0:00 / 0:00
#godelincompleteness#turingmachine#settheory
Math's Fundamental Flaw
Veritasium
21M subscribers • 25 videos on Hallway
- Recommended by 10 people: 7 on Hacker News, 1 on Lobsters and 2 in engineering communities.
Beginner. No background in the topic needed.
30M views5 years ago10 recommendations
Computer scienceHistory and cultureComputation and complexityMath for programmersHistory of computing
Derek Muller explains Gödel's incompleteness theorems, tracing how the limits of mathematical proof led to Turing and modern computing.
Not everything that is true can be proven. This discovery transformed infinity, changed the course of a world war and led to the modern computer. This video is sponsored by Brilliant. The first 200 people to sign up via brilliant.org/veritasium get 20% off a yearly subscription. Special thanks to Prof. Asaf Karagila for consultation on set theory and specific rewrites, to Prof. Alex Kontorovich for reviews of earlier drafts, Prof. Toby ‘Qubit’ Cubitt for the help with the spectral gap, to Henry Reich for the helpful feedback and comments on the video. ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ References: Dunham, W. (2013, July). A Note on the Origin of the Twin Prime Conjecture. In Notices of the International Congress of Chinese Mathematicians (Vol. 1, No. 1, pp. 63-65). International Press of Boston. — ve42.co/Dunham2013 Conway, J. (1970). The game of life. Scientific American, 223(4), 4. — ve42.co/Conway1970 Churchill, A., Biderman, S., Herrick, A. (2019). Magic: The Gathering is Turing Complete. ArXiv. — ve42.co/Churchill2019 Gaifman, H. (2006). Naming and Diagonalization, from Cantor to Godel to Kleene. Logic Journal of the IGPL, 14(5), 709-728. — ve42.co/Gaifman2006 Lénárt, I. (2010). Gauss, Bolyai, Lobachevsky–in General Education?(Hyperbolic Geometry as Part of the Mathematics Curriculum). In Proceedings of Bridges 2010: Mathematics, Music, Art, Architecture, Culture (pp. 223-230). Tessellations Publishing. — ve42.co/Lnrt2010 Attribution of Poincare’s quote, The Mathematical Intelligencer, vol. 13, no. 1, Winter 1991. — ve42.co/Poincare Irvine, A. D., & Deutsch, H. (1995). Russell’s paradox. — ve42.co/Irvine1995 Gödel, K. (1992). On formally undecidable propositions of Principia Mathematica and related systems. Courier Corporation. — ve42.co/Godel1931 Russell, B., & Whitehead, A. (1973). Principia Mathematica [PM], vol I, 1910, vol. II, 1912, vol III, 1913, vol. I, 1925, vol II & III, 1927, Paperback Edition to* 56. Cambridge UP. — ve42.co/Russel1910 Gödel, K. (1986). Kurt Gödel: Collected Works: Volume I: Publications 1929-1936 (Vol. 1). Oxford University Press, USA. — ve42.co/Godel1986 Cubitt, T. S., Perez-Garcia, D., & Wolf, M. M. (2015). Undecidability of the spectral gap. Nature, 528(7581), 207-211. — ve42.co/Cubitt2015 ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ Special thanks to Patreon supporters: Paul Peijzel, Crated Comments, Anna, Mac Malkawi, Michael Schneider, Oleksii Leonov, Jim Osmun, Tyson McDowell, Ludovic Robillard, Jim buckmaster, fanime96, Juan Benet, Ruslan Khroma, Robert Blum, Richard Sundvall, Lee Redden, Vincent, Marinus Kuivenhoven, Alfred Wallace, Arjun Chakroborty, Joar Wandborg, Clayton Greenwell, Pindex, Michael Krugman, Cy 'kkm' K'Nelson, Sam Lutfi, Ron Neal ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ Executive Producer: Derek Muller Writers: Adam Becker, Jonny Hyman, Derek Muller Animators: Fabio Albertelli, Jakub Misiek, Ivy Tello, JonnWhy it's here
10 people recommend thisWhat people say. Recommended as an exceptionally clear and accessible explanation of Gödel's incompleteness theorems and their connection to the foundations of computer science.
Moments people linked to
travisgriggson Hacker News • Recommends
On “How imaginary numbers were invented [video]”
I love Veritasium. Derek has done a number of videos that are awesome like this. The videos are great and educational, but he also manages to subtly weave in an almost spiritual subtext to them as well. For example, in this one, you learn about imaginary numbers in some cool ways, history, how awesome e^ix is, etc, but also this yen-yang balance between embracing not only what is real but taking a chance on what is imaginary. Some of my other favorites: - link - link to this video - link - link - link I think he’s going to lose the $10,000 bet on the car though.
reggiebandon Hacker News • Recommends
On “How inevitable is the concept of numbers?”
…e is a book "The Philosophy of Set Theory" 3 that sketches out how we got to where we are. I have always been unsatisfied with the current foundations of math and their obtuse basis in Set Theory. Although I must admit, Category Theory has alleviated that quite a lot, especially with the relaxing of equivalence compared to equality. 1. link 2. link to this video 3. link…
littlecranky67on Hacker News • Recommends
On “1931: Kurt Gödel shows limits of math, logic, computing, AI”
Veritasium recently released a very good video that explains Gödels incompletenes theorem such that even I could understand it: link to this video
simiason Hacker News • Recommends
On “Where do type systems come from? (2017)”
But what if the statement is "this statement can't be proven"? You haven't proven the statement, you've proven that it can't be proven. See link to this video for instance which is (IMO) a fairly good explanation of the proof and why you end up with something both true and not provable. Penrose's "Emperor's New Mind" also discusses this topic at length (within the context of whether human brains can be emulated). I wasn't convinced with his argument regarding AI but his overview of the problem of what's computable and what's not is rather good if a bit dense.
shagieon Hacker News • Recommends
On “Gödel, Escher, Bach: an in-depth explainer”
Veritasium - Math's Fundamental Flaw link to this video At 13:46 it gets into the "is there a way to prove every complete statement?" and furthermore goes into the Godel math for "there is no proof for the statement with Gödel number g" where that statement itself has a number "g". The entire video is a good watch though. And the related problem is that with Godel we don't know if math is consistent either.
pandoroon Hacker News • Recommends
On “The complete story of Gödel incompleteness”
It's very entry-level (my level :)) but I found Veritaseum's video about it really clear and instructive: link to this video
equanimitivityon Hacker News • Recommends
On “Philosophy is an art”
I used to think similarly, but learning about the proven incompleteness of sufficiently rigorous analytic systems has moved me towards appreciating less rigorous ways of interfacing with reality. Veritasium has a nice video on Godel’s incompleteness theorem. It’s quite ironic that it was mathematically provable that analytic systems can never be complete, and can’t be provably coherent. link to this video
u/squid__pewin r/compsci • Recommends
A great video on Undecidability, The Game of Life, and Turing Machines.
u/TheOtherBorgCubein r/C_Programming • Mentions
On “I want to master C”
A very large board :)\
https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
Then fall down this recursive rabbit hole.\
link to this video
will_byrdon Hacker News • Mentions
On “William Byrd on logic and relational programming, miniKanren (2014)”
…an inference rule returns wrong results. Incompleteness is where it doesn't return all correct results. As you say, unification without an occurs check is unsound and Prolog's depth-first search is incomplete. Thank you. Yes, I misspoke. For anyone interested, this video gives a nice overview of soundness and completeness, in the context of logic: link to this video > I wanted to ask, because you brought it up in the interview, how does minikanren (or minikanrens?) handle the occurs check? You said that you are interested in trying to push the relational aspect as far as possible, recognising that this gives up efficiency - can you quantify to what extent minikanren gives up efficiency and generally sa…
shagieon Hacker News • Mentions
On “Hilbert's Paradox of the Grand Hotel”
This was a pair of videos in Veritasium recently - How An Infinite Hotel Ran Out Of Room - link and Math Has a Fatal Flaw - link to this video .
alok-gon Hacker News • Mentions
On “1931: Kurt Gödel shows limits of math, logic, computing, AI”
…it uses older mathematical notation not in use today. In short, I haven't found any source that explains the proof in reasonable detail. If you want to understand the thought process of axiomatic reasoning (and with less extrapolations to consciousness et al) it is a good book. Note: I had read a long time back, so do not remember the details. 1 link to this video 2 link…
gary17theon Hacker News • Mentions
On “The 3x+1 Problem [video]”
This was a great video. But the one titled "Math Has a Fatal Flaw"1 was even more interesting: the meta-mathematics, thus mathematics of entire mathematics (Gödel). 1 link to this video
galaxyLogicon Hacker News • Mentions
On “New math book rescues landmark topology proof”
I found this nice presentation about Godel's theorems. link to this video "There is no proof for the statement with Godel-number g". What I'm struggling with is trying to understand if self-reference can be formally represented by some symbol. Can it? Godel's proof seems to rely on a trick that allows a formal system to talk about itself but is that possible? There would need to be a symbol for that and thus a symbol that refers to itself? A picture of a pipe is not a pipe. Similarly a representation of a proof is not a proof, is it?. Not saying I believe I'm right and Godel wrong, but it just feel strange to me that a formal system could ever "prove" anything about itself. What does it mean that somet…