Math's Fundamental Flaw

Summary

本文探讨了数学中的不确定性和不可判定性问题，从哥德尔不完备性定理和图灵机的概念出发，解释了为何存在无法证明的真命题。通过康威的生命游戏、量子物理和王瓷砖等例子，展示了不可判定性在不同领域的普遍存在。同时，介绍了数学家如希尔伯特、康托尔、罗素、哥德尔和图灵的贡献，以及他们的工作如何影响了现代计算机科学的诞生和发展。视频由Brilliant赞助，Brilliant是一个提供深入数学、物理和计算机科学主题的互动课程和测验的网站。

Takeaways

• 🧩 数学中存在无法证明的真实陈述，这意味着我们永远无法确定地知道一切。
• 🎲 双生素数猜想是一个可能永远无法证明或证伪的数学猜想，它关于存在无限多对双生素数。
• 🕹 Conway的生命游戏展示了即使规则简单，系统也能产生复杂多变的行为，其模式的最终命运是不可判定的。
• 🔢 Georg Cantor的集合论引入了可数无限和不可数无限的概念，改变了对无穷大的传统理解。
• 📚 David Hilbert的23个问题中的前三个问题关注数学的完备性、一致性和可判定性，但哥德尔的不完备性定理和图灵的停机问题表明数学是既不一致也不可判定的。
• 🤔 哥德尔的不完备性定理表明任何包含基本算术的数学系统都将包含无法证明的真实陈述。
• 🔍 哥德尔的证明利用了自引用和哥德尔数来展示数学系统内部的某些陈述是不可证明的。
• 🚫 图灵的停机问题证明了不存在一种算法能够确定任意图灵机在给定输入下是否会停止运行，这意味着数学是不可判定的。
• 🔗 许多不同的系统，包括物理系统、量子力学、航空票务系统等，都存在不可判定的问题。
• 💡 尽管数学存在不确定性，但对这些问题的思考推动了计算机科学的诞生和发展，影响了现代世界。

Q & A

数学中存在无法确定的陈述意味着什么？

这意味着在数学系统中，有些真实陈述可能永远无法被证明或证伪。这表明数学知识的边界并不是完全确定的，总有一些问题可能超出了我们证明的能力。

双生素数猜想是什么？

双生素数猜想是指存在无限多对相差2的素数对，例如(11, 13)和(17, 19)。尽管素数在数轴上出现的频率逐渐减少，但双生素数猜想认为双生素数对是无限的。

康威的《生命游戏》如何展示了数学的不确定性？

《生命游戏》是一个简单的细胞自动机，通过两个规则在无限大的网格上演化。尽管规则简单，它却能产生复杂的行为模式。游戏的某些模式是不可判定的，意味着不存在一个算法能在有限时间内确定一个模式的最终命运，这展示了数学中的不确定性。

康托尔的对角线论证是如何证明实数比自然数更多的？

康托尔的对角线论证通过构造一个新的实数，该实数与列表中的每个实数在至少一个数字上不同，从而证明了实数集合的基数大于自然数集合的基数，即使两者都是无限的。

直觉主义者对数学的看法是什么？

直觉主义者认为数学是纯粹人类心智的创造，他们反对康托尔的集合论，认为数学应该是确定无疑的，并且反对接受无限集合的概念。

罗素的悖论是什么？

罗素的悖论是通过考虑一个自引用的集合——即包含所有不包含自己的集合的集合——来展示的。这个悖论展示了如果一个集合可以包含自己，那么就会出现逻辑上的矛盾。

图灵的停机问题是什么？

图灵的停机问题是指在没有实际运行程序的情况下，判断一个程序是否会在给定输入上无限循环或者最终停止的问题。这个问题是不可判定的，意味着不存在一个算法能够对所有可能的程序和输入给出正确答案。

哥德尔不完备性定理对数学意味着什么？

哥德尔不完备性定理表明，任何足够强大的数学系统都不可能同时是完备的（每个真实陈述都有证明）和一致的（没有矛盾）。这意味着在数学中，总有一些真实的陈述无法被证明。

为什么现代计算机可以追溯到图灵机的概念？

图灵机是一个抽象的计算模型，它能够模拟任何算法的计算过程。现代计算机的设计基于图灵完备性的概念，即任何图灵机能够执行的计算，现代计算机也能够执行，这使得计算机能够执行广泛的计算任务。

希尔伯特的23个问题是什么？

希尔伯特的23个问题是大卫·希尔伯特在1900年提出的一系列未解决的数学问题，这些问题被认为对20世纪的数学发展有深远的影响。

为什么说数学的底端有一个洞？

这个比喻指的是数学系统中存在一些无法确定的真理，即存在一些真实陈述无法被证明或证伪。这个“洞”表明了数学知识的局限性和不确定性。

哥德尔的不完全性定理对数学家有什么影响？

哥德尔的不完全性定理对数学家产生了深远的影响，它改变了数学家对数学系统完备性和一致性的看法，也促进了对数学基础和逻辑极限的进一步探索。

Outlines

00:00

🔢 数学基础中的不确定性

本段讨论了数学中存在无法证明的真实陈述，如孪生素数猜想，即存在无限对的孪生素数。孪生素数是相差仅一个整数的素数对，例如11和13。尽管素数在数轴上出现的频率逐渐减少，但孪生素数猜想认为它们永远不会耗尽。然而，这个猜想至今未被证明或证伪。更令人惊讶的是，数学系统中存在无法证明的真实陈述，这是由于在任何可以进行基本算术的数学系统中，总有一些真实陈述是无法证明的。

05:00

🎮 康威的生命游戏与不可判定性

康威的生命游戏是一种在无限格子上进行的细胞自动机游戏，每个格子可以是活的或死的，并且遵循两条简单规则：1) 任何死细胞，如果恰好有三个活邻居，就会变成活的；2) 任何活细胞，如果邻居少于两个或多于三个，就会死亡。这个游戏虽然规则简单，但可以产生复杂多变的行为模式，有些模式稳定不变，有些循环振荡，有些如滑翔机模式可以永远穿越网格。然而，确定一个模式最终是稳定还是无限增长的问题，是不可判定的，即不存在有限时间内总能给出答案的算法。

10:04

🔍 哥德尔不完备性定理与数学的局限性

20世纪初，数学家们开始质疑数学的基础。非欧几何的发现和康托尔关于无穷的研究，使得数学家们意识到数学的极限概念定义不清，无穷本身也比想象中复杂。哥德尔的不完备性定理证明了任何能够进行基本算术的数学系统都将包含无法证明的真实陈述，这意味着数学系统无法是完备的。此外，哥德尔的第二不完备性定理表明，任何一致的数学系统不能证明它自身的一致性，因此数学系统可能在未来发现矛盾。

15:07

👨‍💻 图灵机与计算理论

图灵机是图灵为解决希尔伯特的可判定性问题而提出的抽象计算模型，它由一个无限长的纸带、读写头、一组内部状态和转移规则组成。图灵机可以执行任何可计算算法，包括复杂的数学证明和现代计算机算法。图灵通过构造一个停机问题的悖论，证明了不存在一种算法能够确定任意图灵机是否会停机，从而解决了数学的可判定性问题，表明数学是不可判定的。

20:14

🛰️ 不可判定性在现实世界的应用

不可判定性的概念不仅限于数学和逻辑，它也出现在物理、量子力学等领域。例如，量子力学中的能隙问题，即确定一个多体系统是否有能隙，已被证明是不可判定的。这意味着即使完全了解一个物质的微观粒子间的相互作用，也不一定能确定其宏观属性。

25:17

🌐 图灵完备性与现代计算设备

图灵完备性是指一个系统能够执行任何图灵机能够执行的计算。现代计算机和许多编程语言都是图灵完备的，这意味着它们能够执行任何可计算算法。图灵机的概念不仅影响了计算机科学的发展，而且也启发了现代计算设备的设计。

30:17

🕊️ 数学和计算的深远影响

尽管数学存在不确定性和不可判定性，但这并没有导致数学的崩溃，反而激发了对无穷的新理解，改变了第二次世界大战的进程，并直接导致了你现在正在使用的设备——计算机的发明。图灵的计算理论不仅帮助破解了纳粹密码，缩短了战争，还与冯·诺依曼一起设计了世界上第一台可编程电子计算机ENIAC。

Keywords

💡Twin Prime Conjecture

双素数猜想是关于素数分布的一个未解数学问题，它假设有无限对的双素数，即一对素数，它们之间仅相差2，例如(11, 13)和(17, 19)。视频中提到，尽管双素数在自然数中出现的频率逐渐降低，但双素数猜想认为这样的素数对是无限的，且至今没有被证明或反驳，体现了数学中存在无法证明的真实陈述。

💡Game of Life

康威的生命游戏是由英国数学家约翰·霍顿·康威在1970年发明的一种细胞自动机。它在无限的方格网格上进行，每个格子可以是“活”或“死”两种状态，根据两条简单规则进行演化：一是任何死细胞，如果恰好有三个活邻居，就会变成活细胞；二是任何活细胞，如果少于两个或多于三个邻居，就会死去。这个游戏虽然规则简单，但能产生复杂多变的模式，有些模式稳定不变，有些循环振荡，有些则永远移动或增长，展示了简单规则下可能出现的不可预测性和复杂性。

💡Undecidability

不可判定性是指在某些数学系统中存在无法通过任何算法在有限时间内判定的问题。视频中提到，康威的生命游戏的最终命运是不可判定的，意味着不存在一个算法能够保证对游戏中的任何模式最终状态给出答案。此外，不可判定性也出现在其他系统中，如量子物理、机票预订系统等，这表明不可判定性是一个普遍现象。

💡Georg Cantor

格奥尔格·康托尔是德国数学家，集合论的创始人。他在1874年发表了关于集合论的论文，提出了自然数集和实数集大小的比较问题，并通过著名的对角线论证法证明了实数集比自然数集有“更多”的元素，即存在不可数无限集。康托尔的工作对数学的基础产生了深远影响，引发了数学界的大辩论，并为后来的逻辑和计算机科学奠定了基础。

💡Set Theory

集合论是数学的一个分支，研究集合（即明确定义的事物集合）。康托尔在1874年发表的论文中提出了集合论，它成为了现代数学的基础之一。集合论不仅研究集合的大小，还研究集合之间的运算和关系。集合论的发展对数学产生了革命性的影响，尤其是在理解无限概念方面。

💡David Hilbert

大卫·希尔伯特是德国数学家，对20世纪初的数学发展产生了巨大影响。他提出了著名的希尔伯特的23个问题，这些问题指导了一个世纪的数学研究。希尔伯特主张形式主义，认为数学可以建立在集合论等牢固的逻辑基础之上。他试图通过形式系统来解决数学的完整性、一致性和可判定性问题，但哥德尔的不完全性定理证明了希尔伯特的形式系统无法实现其目标。

💡Gödel's Incompleteness Theorems

哥德尔的不完全性定理是逻辑和数理逻辑中的重要发现，由库尔特·哥德尔在1931年提出。第一不完全性定理表明在任何包含基本算术的一致形式系统内，都存在这样的命题：这个命题既不能被证明为真，也不能被证明为假。第二不完全性定理指出，一个系统如果是一致的，它就无法证明自身的一致性。哥德尔的定理对希尔伯特的形式主义计划产生了致命打击，表明了数学系统的局限性。

💡Turing Machine

图灵机是由艾伦·图灵提出的一种抽象计算模型，用于定义什么是可计算的。图灵机由一个无限长的纸带、一个读写头、一套控制规则和一个状态寄存器组成。它可以模拟任何算法过程，是现代计算机的基础。图灵机的概念帮助证明了数学的不可判定性问题，即不存在一个通用算法来确定一个给定的数学命题是否可证明。

💡Alan Turing

艾伦·图灵是英国数学家、逻辑学家、密码学家，被誉为计算机科学和人工智能之父。在第二次世界大战期间，图灵在布莱切利园领导了一个团队，成功破解了德国的恩尼格玛密码机，对战争胜利起到了重要作用。战后，图灵继续在计算机科学领域工作，参与了早期计算机的设计与开发。然而，由于当时英国对同性恋的法律歧视，图灵被迫接受化学阉割，并在1954年自杀。

💡Halting Problem

停机问题是图灵在研究可计算性理论时提出的一个著名问题，即判断一个图灵机是否会在有限步骤后停止，或者它会无限循环下去。图灵证明了停机问题是不可解的，即不存在一个通用算法能够预测所有程序在所有可能的输入下是否停机。这个问题与数学的可判定性问题紧密相关，也是现代计算机科学中的一个基本概念。

Highlights

数学中存在一个无法确定的洞，意味着我们永远无法确定地知道一切，总有一些真实的陈述无法被证明。

双生素数猜想是关于存在无限多对双生素数的猜想，但至今未被证明或证伪。

哥德尔证明了在任何可以进行基本算术的数学系统中，总会有一些真实陈述是无法证明的。

康威的生命游戏是一个简单的零玩家游戏，但能产生复杂多变的行为模式。

生命游戏中的模式最终命运是不可判定的，没有算法能在有限时间内确定其命运。

哥德尔的不完全性定理表明，任何能够进行基本算术的数学系统都将包含无法证明的真实陈述。

图灵机是现代计算机的基础，它展示了计算的本质和限制。

图灵证明了停机问题是不可判定的，即无法总是确定一个程序是否会停止。

希尔伯特的23个问题中的前三个问题关注数学的完备性、一致性和可判定性。

哥德尔的不完全性定理和图灵的停机问题表明数学可能既不一致也不完备，且不可判定。

量子力学中的能隙问题也是不可判定的，表明物理系统也存在类似数学的复杂性。

图灵完备性表明，任何足够强大的计算系统都包含类似停机问题的不可判定问题。

康威的生命游戏在图灵机内部运行，展示了自我模拟的能力。

希尔伯特的梦想和哥德尔、图灵的工作最终导致了现代计算设备的发明。

哥德尔和图灵的个人生活遭遇反映了他们所处时代的社会问题。

数学中的不确定性和不可判定性并没有导致数学的崩溃，反而推动了新发现和计算机科学的诞生。

Brilliant网站提供深入的互动课程和测验，帮助人们探索数学、物理和计算机科学等领域。

Transcripts

There is a hole at the bottom of math

a hole that  means we will never know everything with certainty

There will always be true statements that  cannot be proven.

Now no one knows what those statements are exactly

but they could be something like the Twin Prime Conjecture.

Twin primes are prime numbers that are separated  by just one number like 11 and 13, or 17 and 19.

And as you go up the number line primes occur less  frequently and twin primes are rarer still.

But the Twin Prime Conjecture is that there are infinitely  many twin primes.

You never run out them.

As of right now no one has proven this conjecture true or false.

But the crazy thing is this: we may never know

because what has been proven is that in any system  of mathematics where you can do basic arithmetic

there will always be true statements  that are impossible to prove.

That is life.

Specifically this is the Game of Life,  created in 1970 by mathematician John Conway

Sadly he passed away in 2020 from covet  19. Conway's game of life is played on an

infinite grid of square cells each of which is  either live or dead and there are only two rules

one any dead cell with exactly three neighbors  comes to life and two any living cell with less

than two or more than three neighbors dies once  you've set up the initial arrangement of cells

the two rules are applied to create the  next generation and then the one after that

and the one after that and so on it's totally  automatic Conway called it a zero player game

but even though the rules are simple the game  itself can generate a wide variety of behavior

some patterns are stable once they arise they  never change others oscillate back and forth in a

loop a few can travel across the grid forever like  this glider here many patterns just fizzle out

but a few keep growing forever  they keep generating new cells

now you would think that given the  simple rules of the game you could just

look at any pattern and determine what will happen  to it will it eventually reach a steady state

or will it keep growing without limit but it  turns out this question is impossible to answer

the ultimate fate of a pattern in Conway's  game of life is undecidable meaning there

is no possible algorithm that is guaranteed to  answer the question in a finite amount of time

you could always just try running the pattern and  see what happens i mean the rules of the game are

a kind of algorithm after all but that's not  guaranteed to give you an answer either because

even if you run it for a million generations  you won't be able to say whether it'll last

forever or just 2 million generations  or a billion or a googleplex

is there something special about the game of life  that makes it undecidable nope there are actually

a huge number of systems that are undecidable  like Wang tiles quantum physics airline ticketing

systems and even magic the gathering to understand  how undecidability shows up in all of these places

we have to go back 150 years to a  full-blown revolt in mathematics

in 1874 Georg Cantor a german mathematician  published a paper that launched a new branch

of mathematics called set theory a set is  just a well-defined collection of things

so the two shoes on your feet are a set as are  all the planetariums in the world there's a set

with nothing in it the empty set and a set with  everything in it now Cantor was thinking about

sets of numbers like natural numbers positive  integers like 1 2 3 4 and so on and real numbers

which include fractions like a third five  halves and also irrational numbers like pi e

and the square root of two basically any number  that can be represented as an infinite decimal

he wondered are there more natural numbers  or more real numbers between zero and one

the answer might seem obvious there are  an infinite number of each so both sets

should be the same size but to check this logic  canter imagined writing down an infinite list

matching up each natural number on one side with  a real number between zero and one on the other

now since each real number is an infinite decimal  there is no first one so we can just write them

down in any random order the key is to make sure  we get them all with no duplicates and line them

up one to one with an integer if we can do that  with none left over well then we know that the

set of natural numbers and the set of real numbers  between 0 and 1 are the same size so assume we've

done that we have a complete infinite list with  each integer acting like an index number a unique

identifier for each real number on the list now  Cantor says start writing down a new real number

and the way we're going to do it is by taking the  first digit of the first number and adding one

then take the second digit of the second number  and again add one take the third digit of the

third number add one and keep doing this all the  way down the list if the digit is a nine just roll

it back to an eight and by the end of this process  you'll have a real number between zero and one but

here's the thing this number won't appear anywhere  on our list it's different from the first number

in the first decimal place different from the  second number in the second decimal place and

so on down the line it has to be different from  every number on the list by at least one digit

the number on the diagonal that's why this  is called Cantor's diagonalization proof

it shows there must be more real numbers between  0 and 1 then there are natural numbers extending

out to infinity so not all infinities are the same  size Cantor call these countable and uncountable

infinities respectively and in fact there are many  more uncountable infinities which are even larger

now Cantor's work was just the latest blow to  mathematics for 2000 years Euclid's elements

were considered the bedrock of the discipline but  at the turn of the 19th century Lobashevsky and

gauss discovered non-Euclidean geometries and  this prompted mathematicians to examine more

closely the foundations of their field and they  did not like what they saw the idea of a limit

at the heart of calculus turned out to be poorly  defined and now Cantor was showing that infinity

itself was much more complex than anyone had  imagined in all this upheaval mathematics

fractured and a huge debate broke out among  mathematicians at the end of the 1800s on the

one side were the intuitionists who thought that  Cantor's work was nonsense they were convinced

that math was a pure creation of the human mind  and that infinities like Cantors weren't real

Henri Poincaré said that later generations will  regard set theory as a disease from which one

has recovered Leopold Kronecker called Cantor a  scientific charlatan and a corrupter of the youth

and he worked to keep Cantor from getting a job  he wanted on the other side were the formalists

they thought that math could be put on absolutely  secure logical foundations through Cantor's set

theory the informal leader of the formalists  was the german mathematician David Hilbert

Hilbert was a living legend a hugely influential  mathematician who had worked in nearly every area

of mathematics he almost beat Einstein to the  punch on general relativity he developed entirely

new mathematical concepts that were crucial for  quantum mechanics and he knew that Cantor's work

was brilliant Hilbert was convinced that a more  formal and rigorous system of mathematical proof

based on set theory could solve all the issues  that had cropped up in math over the last century

and most other mathematicians agreed with him no  one shall expel us from the paradise that Cantor

has created Hilbert declared but in 1901 Bertrand  Russell pointed out a serious problem in Cantor's

set theory Russell knew that if sets can contain  anything they can contain other sets or even

themselves for example the set of all sets must  contain itself as does the set of sets with more

than five elements in them you could even talk  about the set of all sets that contain themselves

but this leads straight to a problem what about r  the set of all sets that don't contain themselves

if r doesn't contain itself well then it must  contain itself but if r does contain itself

then by definition it must not contain itself so r  contains itself if and only if it doesn't Russell

had found another paradox of self-reference and  he later explained his paradox using a hairy

analogy let's say there's a village populated  entirely by grown men with a strange law against

beards specifically the law states that the  village barber must shave all and only those men

of the village who do not shave themselves but the  barber himself lives in the village too of course

and he's a man so who shaves him if he doesn't  shave himself then the barber has to shave him

but the barber can't shave himself because the  barber doesn't shave anyone who shaves themselves

so the barber must shave himself if and only if  he doesn't shave himself it's a contradiction

the intuitionists rejoiced at Russell's  paradox thinking it had proven set theory

hopelessly flawed but zermelo and other  mathematicians from Hilbert school

solved the problem by restricting the concept of  a set so the collection of all sets for example is

not a set anymore and neither is the collection  of all sets which don't contain themselves

this eliminated the paradoxes that  come with self-reference Hilbert and

the formalists lived to fight another day but  self-reference refused to die quite that easily

fast forward to the 1960s and mathematician Hao  Wang was looking at square tiles with different

colors on each side like these the rules were  that touching edges must be the same color

and you can't rotate or reflect tiles only slide  them around the question was if you're given an

arbitrary set of these tiles can you tell if they  will tile the plane that is will they connect

up with no gaps all the way out to infinity it  turns out you can't tell for an arbitrary set of

tiles whether they will tile the plane or not  the problem is undecidable just like the fate

of a pattern in Conway's game of life in fact  it's exactly the same problem and that problem

ultimately comes from self-reference as Hilbert  and the formalists were about to discover

Hilbert wanted to secure the foundations of  mathematics by developing a new system for

mathematical proofs systems of proof were an old  idea going back to the ancient greeks a system of

proof starts with axioms basic statements that  are assumed to be true like a straight line can

be drawn between any two points proofs are then  constructed from those axioms using rules of

inference methods for using existing statements  to derive new statements and these are chosen to

preserve truth the existing statements are true  then so are the new ones Hilbert wanted a formal

system of proof a symbolic logical language with a  rigid set of manipulation rules for those symbols

logical and mathematical statements could then  be translated into this system if you drop a

book then it will fall would be a then b and no  human is immortal would be expressed like this

Hilbert and the formalists wanted to express  the axioms of mathematics as symbolic statements

in a formal system and set up the rules  of inference as the system's rules for

symbol manipulation so Russell  along with Alfred North Whitehead

developed a formal system like this in  their three-volume Principia Mathematica

published in 1913. Principia Mathematica is vast a  total of nearly 2 000 pages of dense mathematical

notation it takes 762 pages just to get to a  complete proof that one plus one equals two

at which point Russell and Whitehead dryly note  the above proposition is occasionally useful

the authors had originally planned  a fourth volume but unsurprisingly

they were too worn out to complete it so yes  the notation is dense and exhausting but it is

also exact unlike ordinary languages it leaves  no room for errors or fuzzy logic to creep in

and most importantly it allows you to prove  properties of the formal system itself

there were three big questions that  Hilbert wanted answered about mathematics

number one is math complete meaning is there a  way to prove every true statement does every true

statement have a proof number two is mathematics  consistent meaning is it free of contradictions

i mean if you can simultaneously prove a and not  a then that's a real problem because you can prove

anything at all and number three is math  decidable meaning is there an algorithm that

can always determine whether a statement follows  from the axioms now Hilbert was convinced that

the answers to all three of these questions was  yes at a major conference in 1930 Hilbert gave

a fiery speech about these questions he ended it  with a line that summed up his formalist dream in

opposition to the foolish ignorabimus which means we  will not know our slogan shall be we must know we

will know these words are literally on his grave  but by the time Hilbert gave this speech his dream

was already crumbling just the day before at a  small meeting at the same conference a 24 year old

logician named Kurt Gödel explained that he had  found the answer to the first of Hilbert's three

big questions about completeness and the answer  was no a complete formal system of mathematics

was impossible the only person who paid much  attention was John von Neumann one of Hilbert's

former students who pulled Gödel aside to ask a  few questions but the next year Gödel published

a proof of his incompleteness theorem and this  time everyone including Hilbert took notice

this is how Gödel's proof works Gödel  wanted to use logic and mathematics

to answer questions about the very system  of logic and mathematics and so he took

all these basic symbols of a mathematical  system and then he gave each one a number

this is known as the symbol's Gödel number  so the symbol for not gets the number one

or has the Gödel number two if then it's Gödel  number three now if you're expressing all of these

symbols with numbers then what do you do about  the numbers themselves well zero gets its own

Gödel number six and if you want to write a one  you just put this successor symbol next to it the

immediate successor of zero is 1. and if you  want to write 2 then you have to write ss0

and that represents 2 and so on so you could  represent any positive integer this way

granted it is cumbersome but it works  and that is the point of this system

so now that we have Gödel numbers for all of  the basic symbols and all of the numbers we might

want to use we can start to write equations  like we could write zero equals zero so these

symbols have the Gödel numbers six five six and  we can actually create a new card that represents

this equation zero equals zero and the way we  do it is we take the prime numbers starting at 2

and we raise each one to the power of the Gödel  number of the symbol in our equation so we have

2 to the power of 6 times 3 to the power of 5  times 5 to the power of 6 equals 243 million

so 243 million is the Gödel number  of the whole equation zero equals

zero we can write down Gödel numbers for  any set of symbols that you can imagine

so really this is an infinite deck of cards where  any set of symbols that you want to write down

in a sequence you can represent with a unique  Gödel number and the beauty of this Gödel

number is you can do a prime factorization of it  and you can work out exactly what symbols made up

this card so in this whole pack of cards  there are going to be true statements

and there are going to be false statements so how  do you prove that something is true well you need

to go to the axioms the axioms also have their own  Gödel numbers which are formed in the same way

so here's an axiom which says not the successor of  any number x equals zero which makes sense because

in this system there are no negative numbers and  so the successor of any number cannot be zero

so we can put down this axiom and then we can  substitute in zero for x saying that one does not

equal zero and we've created a proof this is the  simplest proof i can think of that shows that one

does not equal zero now this card for the proof of  one does not equal zero gets its own Gödel number

and the way we calculate this Gödel number  is just as before we take the prime numbers

and we raise 2 to the power of the axiom times  3 to the power of 1 does not equal 0 and we get

a tremendously large number it would have 73  million digits if you calculated it all out so

i've just left it here in exponential notation as  you can see these numbers get very large and so

you might want to start just calling them by  letters so we could say this one is Gödel

number a this is Gödel number b Gödel number  c and so on Gödel goes to all this trouble to find

this card which says there is no proof for the  statement with Gödel number g the trick is

that the Gödel number of this card is  g so what this statement is really saying

is this card is unprovable there is no proof  anywhere in our infinite deck for this card

now think about it if it's  false and there is a proof

then what you have just proven is there is  no proof so you're stuck with a contradiction

that would mean the mathematical system is  inconsistent the other alternative is that

this card is true there is no proof for the  statement with Gödel number g but that means

this mathematical system has true statements  in it that have no proof so your mathematical

system is incomplete and that is Gödel's  incompleteness theorem this is how he shows

that any basic mathematical system that can do  fundamental arithmetic will always have statements

within it which are true but which have no proof  there's a line in the tv show the office that

echoes the self-referential paradox of Gödel's  proof jim is my enemy but it turns out the jim

is also his own worst enemy and the enemy of my  enemy is my friend so jim is actually my friend

but because he is his own worst enemy the enemy

of my friend is my enemy so  actually jim is my enemy but

Gödel's incompleteness theorem means that  truth and provability are not at all the same

thing Hilbert was wrong there will always be true  statements about mathematics that just cannot

be proven now Hilbert could console himself with  the hope that at least we could still prove maths

consistent that is free of contradictions  but then Gödel published his second

incompleteness theorem in which he showed  that any consistent formal system of math

cannot prove its own consistency so taken together  Gödel's two incompleteness theorems say that the

best you can hope for is a consistent yet  incomplete system of math but a system like

that cannot prove its own consistency so some  contradiction could always crop up in the future

revealing that the system you'd been working with  had been inconsistent the whole time and that

leaves only the third and final big question from  Hilbert is mathematics decidable that is is there

an algorithm that can always determine whether  a statement follows from the axioms and in 1936

Alan Turing found a way to settle this question  but to do it he had to invent the modern computer

in his time computers weren't machines  they were people often women who carried

out long and tedious calculations Turing  imagined an entirely mechanical computer

he wanted it to be powerful enough to perform any  computation imaginable but simple enough that you

could reason through its operation so he came up  with a machine that takes as input an infinitely

long tape of square cells each containing a zero  or a one the machine has a read write head that

can read one digit at a time then it can perform  one of only a few tasks overwrite a new value

move left move right or simply halt  halting means the program has run

to completion the program consists of a set of  internal instructions you can think of it like

a flow chart that tells the machine what to do  based on the digit it reads and its internal state

you could imagine exporting these instructions to  any other Turing machine which would then perform

in exactly the same way as the first although  this sounds simple a Turing machine's arbitrarily

large memory and program mean it can execute any  computable algorithm if given enough time from

addition and subtraction to the entire youtube  algorithm it can do anything a modern computer can

that's what made the Turing machine so useful in  answering Hilbert's question on decidability when

a touring machine halts the program has finished  running and the tape is the output but sometimes a

touring machine never halts maybe it gets stuck in  an infinite loop is it possible to tell beforehand

if a program will halt or not on a particular  input Turing realized this halting problem

was very similar to the decidability problem if  he could find a way to figure out if a Turing

machine would halt then it would also be possible  to decide if a statement followed from the axioms

for example you could solve the twin prime  conjecture by writing a Turing machine program

that starts with the axioms and constructs  all theorems that can be produced in one step

using the rules of inference then it constructs  all theorems that can be produced in one step

from those and so on each time it generates a  new theorem it checks if it's the twin prime

conjecture and if it is it halts if not it never  halts so if you could solve the halting problem

you could solve the twin prime conjecture  and all sorts of other unsolved questions

so Turing said let's assume we can make a  machine h that can determine whether any

Turing machine will halt or not on a particular  input you insert the program and its input

and h simulates what will happen printing out  either halts or never halts for now we don't worry

about how h works we just know that it always  works it always gives you the right answer now

we can modify the h machine by adding additional  components one if it receives the output halts

immediately goes into an infinite loop another if  it receives never holds then it immediately halts

we can call this entire new machine h plus and  we can export the program for that entire machine

now what happens if we give this machine  its own code both as program and input

well now h is simulating what h plus  would do given its own input essentially h

has to determine the behavior of a machine  that it itself is a part of in this exact

circumstance if h concludes that h plus never  halts well this makes h plus immediately halt

if h thinks h plus will halt well then  that necessarily forces h plus to loop

whatever output the halting machine h gives it  turns out to be wrong there's a contradiction

the only explanation can be that a machine like  h can't exist there's no way to tell in general

if a touring machine will halt or not on a given  input and this means mathematics is undecidable

there is no algorithm that can always determine  whether a statement is derivable from the axioms

so something like the twin prime conjecture  might be unsolvable we might never know

whether there are infinite twin primes or not  the problem of undecidability even crops up

in physical systems in quantum mechanics one  of the most important properties of a many-body

system is the difference in energy between  its ground state and its first excited state

this is known as the spectral gap some systems  have a significant spectral gap whereas others

are gapless there are a continuum of energy levels  all the way down to the ground state and this is

important because at low temperatures gapless  quantum systems can undergo phase transitions

while gapped systems cannot they don't have  the energy needed to overcome the spectral gap

but figuring out if a system is gapped or gapless  has long been known to be a very difficult

problem only recently in 2015 did mathematicians  prove that in general the spectral gap question

is undecidable to quote the authors even a  perfect complete description of the microscopic

interactions between a material's particles is not  always enough to deduce its macroscopic properties

now remember that Turing designed his machines to  be as powerful computers as it is possible to make

to this day the best computational systems are  those that can do everything a touring machine can

this is called touring completeness and it turns  out there are many such during complete systems

although they are powerful every touring complete  system comes with a catch its own analog of the

halting problem some undecidable property of  the system Wang tiles are touring complete their

halting problem is whether or not they'll tile the  plane complex quantum systems are Turing complete

and their halting problem is the spectral gap  question and the game of life is Turing complete

its halting problem is literally whether or  not it halts there are many more examples

of this like airline ticketing systems magic the  gathering powerpoint slides and excel spreadsheets

nearly every programming language in existence is  designed to be Turing complete but in theory we

only need one programming language because  well you can program anything at all using

any Turing complete system so here's a touring  machine inside the game of life and since the

game of life is itself touring complete it should  be capable of simulating itself and indeed it is

this is the game of life  running on the game of life

the real legacy of David Hilbert's dream  is all of our modern computational devices

Kurt Gödel suffered bouts of mental instability  later in life convinced that people were trying

to poison him he refused to eat eventually  starving himself to death Hilbert died in 1943

his epitaph was his slogan from 1930. we must know  we will know the truth is we don't know sometimes

we can't know but in trying to find out we can  discover new things things that change the world

Alan Turing put his ideas about computing to  practical use in world war ii leading the team

at Bletchley Park that built real calculating  machines to crack nazi codes for the allies

by one estimate the intelligence Turing and  his colleagues gathered from decrypted messages

shortened the war by two to four years after  the war Turing and John von Neumann designed

the first true programmable electronic  computer eniac based on touring's designs

but Turing didn't live to see  his ideas develop much further

in 1952 the british government convicted him of  gross indecency upon learning he was gay he was

stripped of his security clearance and forced  to take hormones in 1954 he committed suicide

touring changed the world he is widely  considered to be the most important founding

figure in computer science all modern  computers are descended from his designs

but touring's ideas about computability  came from his concept of the Turing machine

which came from thinking about Hilbert's question  is math decidable so touring's code breaking

machines and indeed all modern computers stem from  the weird paradoxes that arise from self-reference

there is a hole at the bottom of math a hole that  means we will never know everything with certainty

there will always be true  statements that cannot be proven

and you might think this realization  would have driven mathematicians mad

and led to the disintegration of the entire  mathematical enterprise but instead thinking

about this problem transformed the concept  of infinity changed the course of a world war

and led directly to the invention of the  device you're watching this on right now

hey this video was sponsored by brilliant a  website full of interactive courses and quizzes

that delve deep into topics like math physics and  computer science now if you've gotten this far

into this video you're likely someone who would  love brilliant i've been going through their

logic course and it's really got me thinking  the problems start out easy but get more and

more challenging as you develop your understanding  and that's what i love about the site i love how

it guides you not by telling you exactly but by  exposing you to increasingly sophisticated puzzles

and at the end i feel like i've worked it out  for myself which essentially i have through

their carefully curated selection of problems  and with helpful hints and explanations for

when i get stuck now there were a lot of things  i wanted to include in this video but couldn't

because it's already over half an hour long so if  you want to explore these ideas further i'd highly

recommend their courses on number theory and  computer science fundamentals for viewers of this

channel brilliant are offering 20 off an annual  subscription to the first 200 people to sign up

just go to brilliant.org veritasium and i  will put that link down in the description

so i want to thank brilliant for sponsoring  veritasium and i want to thank you for watching