未登录,请登录后再发表信息
最新评论 (0)
播放视频

数学的致命缺陷

Math Has a Fatal Flaw

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
孪生素数是指相差2的素数对
like 11 and 13, or 17 and 19.
比如11和13 或17和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.
永远无法穷举
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
具体点说 比如由数学家约翰·康威在1970年发明的生命游戏
Sadly he passed away in 2020 from covid 19.
不幸的是他在2020年因感染新冠去世
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.
周围存活的细胞少于2个 或多于3个时 该细胞死亡
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 game of life is undecidable
我们无法确定生命游戏中 某个种群的最终命运
meaning there is no possible algorithm
也就是说 没有有效的算法
that is guaran 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
因为即使这个种群演化了100万代
you won’t be able to say whether it’ll last forever
你也不能说它是否会永远持续下去
or just 2 million generations, or a billion, or a googleblex
或者在二百万代 或十亿代 或者很久很久以后 它仍会消亡
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
我们要追溯到150年前 数学界一次里程碑式的进步
in 1874 Georg Cantor a German mathematician published a paper
1874年 德国数学家乔治·康托发表了一篇论文
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
像1 2 3 4之类
and real numbers which include fractions like a third five halves
再如实数 它包括三分之一 五又二分之一等分数
and also irrational numbers like pi e and the square root of two
以及无理数 比如π e 2的平方根
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
他提出 自然数与0和1之间的实数相比 谁更多呢
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
与另一侧介于0和1之间的实数进行匹配
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
与0和1之间的实数集合 是同样的规模
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
这次的方式是取第一个数字的第一个数位 加上1
then take the second digit of the second number and again add one
之后取第二个数字的第二个数位 也加上1
take the third digit of the third number add one
然后第三个数字的第三个数位 加1
and keep doing this all the way down the list
持续这样进行直到完成清单
if the digit is a nine just roll it back to an eight
如果数位取到了9 接下来就滚动往回取第8个数位
and by the end of this process you’ll have a real number between zero and one
完成全部过程后 你会得到一个介于0和1之间的实数
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
这表明0和1之间的实数一定比
than 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
2000年来 欧氏几何元素被认为是数学学科的基本原理
but at the turn of the 19th century
但是在19世纪之交
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
19世纪 数学家之间爆发了一场广泛的辩论
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
但是1901年 贝特朗·罗素指出了
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.
包含所有“元素个数不少于5的集合”的集合也必须包含自身
You could even talk 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?
如果把R定义为 包含所有“不包含自身的集合”的集合呢
if R doesn’t contain itself,
如果R没有包括自身
well then it must contain itself,
那么它必须把自身包含进去
but if r does contain itself, then by definition it must not contain itself.
但是如果R确实包括了自身 那么根据前述定义 它必须不包括自身
So r contains itself if and only if it doesn’t.
所以R包含自身 当且仅当它不包含自身
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
快进到20世纪60年代
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 plain,
你是否能够判断出他们能否镶嵌出一个平面
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.
他们在1913年出版的三卷《数学原理》中
Principia Mathematica is vast, a total of nearly
《数学原理》是一部巨著
2 000 pages of dense mathematical notation.
里面有近2000页的数学符号
It takes 762 pages just to get to a complete proof that one plus one equals two
仅1加1等于2的完整证明就用了762页
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 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,
我是说如果你可以同时证明A和非A
then that’s a real problem, because you can’t prove it 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 answers to all three of these questions was yes.
希尔伯特认为这三个问题的答案都是肯定的
At a major conference in 1930 Hilbert gave a fiery speech about these questions,
在1930年的一个重大会议上 希尔伯特关于这三个问题发表了激烈的演说
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
一位24岁名叫库尔特·哥德尔的逻辑学家
explained that he had found the answer to the firs
解释说 他发现了关于希尔伯特的
t 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
“~”符号是数字1
or has the Gödel number two if then it’s Gödel number three
“∨”符号是哥德尔数2 “⊃”符号是哥德尔数3
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,
0的哥德尔数是6 如果你想表达1就把这个后继符号放在旁边
the immediate successor of zero is 1. and if you want to write 2 then you have to write ss0
0的直接后继是1 如果你想表达2 就必须用“ss0”
and that represents 2 and so on. So you could represent any positive integer this way.
这就代表2 以此类推 你可以用这种方式表达任意正整数
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.
我们可以写方程了 例如 我们可以写 0=0
So these symbols have the Gödel numbers six five six,
用哥德尔数去表达这些符号就是 6 5 6
and we can actually create a new card that represents this equation zero equals zero,
实际上我们可以用一张新的卡片去代表这个0=0的方程
and the way we do it is we take the prime numbers starting at 2
我们做的方式就是用从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
这样就是2的6次幂 乘以3的5次幂
times 5 to the power of 6 equals 243 million
乘以5的6次幂 最后等于243,000,000
so 243 million is the Gödel number of the whole equation zero equals zero
243,000,000就是整个0=0这个方程式的哥德尔数
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,
任何数的后继数都不为0
which makes sense
这很合理
because in this system there are no negative numbers
因为在这个系统中没有负数
and so the successor of any number cannot be zero
所以任何数的后继数都不会是0
so we can put down this axiom
我们可以先放下这个公理
and then we can substitute in zero for x saying that one does not equal zero,
然后我们用0代替X 这样变成1不等于0
and we’ve created a proof this is the simplest proof,
这样我们就已经建立了一个最简单的证明
I can think of that shows that one does not equal zero.
我可以认为这表明1不等于0
Now this card for the proof of one does not equal zero gets its own Gödel number,
现在这张证明1不等于0的卡片得到它自己的一个哥德尔数
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
我们把2的5次幂 乘以3的1次幂不等于0的幂
and we get a tremendously large number.
这样我们就得到一个极大的数字 如果全部算出来
It would have 73 million digits if you calculated it all out.
这个数字有73,000,000位
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
那么我们可以把这个称为哥德尔数A
this is Gödel number B Gödel number C and so on
这个是哥德尔数B 哥德尔数C 以此类推
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
上面写着 哥德尔数G的命题没有证据
the trick is that the Gödel number of this card is G.
诡异之处在于 这张卡片的哥德尔数就是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
这张卡片是真的 没有证据证明哥德尔数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 lion 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,
1936年 阿兰·图灵发现了解决这个问题的方法
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
每个单元格包含一个0或一个1
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,
从加减法到整个YouTube算法
it can do anything a modern computer can.
任何现代计算机可以做的它都可以做
That’s what made the Turing machine so useful in answering Hilbert’s question on decidability
这就是为什么图灵计算机在回答Hilbert关于可决定性的问题时如此有用
When a Turing machine halts the program has finished running and the tape is the output,
当图灵计算机停止运行时 程序运行终止 磁带就是输出
But sometimes a Turing machine never halts maybe it gets suck 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
于是图灵就说 假设我们可以制造一个叫做h的机器 这个机器可以确定
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.
然后h模拟可能发生的情况 输出的结果要么是停止 要么是永不停止
For now we don’t worry about how h works,
目前 我们无需担心h是如何运行的
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.
我们可以通过加入附加组件来调整h机器
One if it receives the output halts
一种是当它收到的结果是停止运行
immediately goes into an infinite loop,
将立即进入无限循环
another if it receives never halts, then it immediately halts.
另一种是如果它收到的结果是永不停止 就立即停止运行
We can call this entire new machine h plus,
我们可以把这个全新的机器叫做h+
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
现在h正在模拟h+在自己的输入下会做什么
has to determine the behavior of a machine that it itself is a part of in this exact circumstance
特别是h必须决定 在它自己作为其中一个部分的情况下 h+会做什么
if h concludes that h plus never halts well this makes h plus immediately halt
如果h总结说h+永不会停止 那么这就会导致h+马上停止
if h thinks h plus will halt well then that necessarily forces h plus to loop
如果h认为h+将会停止运行 那么这就会迫使h+进入循环
whatever output the halting machine h gives it turns out to be wrong
不管结论是什么 停止的机器h给出的结果都被证明是错的
there’s a contradiction
这里总是有个矛盾
the only explanation can be that a machine like h can’t exist
对此唯一的解释就是 一个h这样的机器不可能存在
there’s no way to tell in general if a Turing 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.
直到最近 在2015年才有数学家证明 通常来说 谱隙问题是不可判定的
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 Turing machine can.
迄今为止 最好的计算系统是那些能做图灵计算机所能做的一切的系统
This is called Turing completeness, and it turns out there are many such during complete systems.
这被称为图灵完备 事实证明 这样的图灵完备系统有很多
Although they are powerful, every Turing complete system comes with a catch,
尽管他们很强大 但每个图灵完备系统都有一个陷阱
its own analog of the halting problem, some undecidable property of the system.
那就是它自身模拟的停机问题 关乎系统的不可判定性
Wang tiles are Turing complete,
王浩瓷砖也是一种图灵完备的系统
their halting problem is whether or not they’ll tile the plain.
他们的停机问题在于他们是否能够完成拼图
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…
像是航空订票系统 万智牌 PPT Excel表格
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 Turing machine inside the game of life,
生命游戏里有一个图灵机
and since the game of life is itself Turing 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
希尔伯特 逝于1943年
his epitaph was his slogan from 1930.
他的墓志铭就是他1930年提出的口号
we must know we will know
我们必须知道 我们必将知道
the truth is we don’t know
而事实是 我们确实不知道
sometimes 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.
将战争缩短了2-4年
After the war Turing and John von Neumann designed
战后 图灵和约翰·冯·诺依曼
the first true programmable electronic computer ENIAC based on Turing’s designs
基于图灵的构想 设计出了第一台真正的可编程电子计算机ENIAC
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
1952年 英国政府在得知他是同性恋后 判处他严重猥亵罪
he was stripped of his security clearance and forced to take hormones
他被剥夺了安全许可 并被强制服用激素
in 1954 he committed suicide
1954年他自杀了
Turing 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 Turing’s ideas about computability came from his concept of the Turing machine
但图灵关于可计算性的概念起源于他的图灵计算机
which came from thinking about Hilbert’s question is math decidable
而图灵计算机来源于对Hilbert关于数学可判定性问题的思考
so Turing’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
这个视频由Brilliant赞助 Brilliant是一个充满互动课程和测验的网站
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
如果你已经看到了这里 那你很可能非常喜欢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 brilliant are offering 20 off an annual subscription to the first 200 people to sign up
Brilliant为前200位注册的用户提供20%的年度订阅折扣
just go to brilliant.org/veritasium and i will put that link down in the description
登录brilliant.org/veritasium 我把链接放在了下方的简介中
so i want to thank brilliant for sponsoring veritasium and i want to thank you for watching
感谢Brilliant赞助Ve元素 感谢观看

发表评论

译制信息
视频概述

数学是严谨的缜密的,但数学中也存在无法证明的命题。而求证这些无法证明的命题的过程中发展出的理论,也使数学、计算机科学等各种相关领域不断进步。

听录译者

收集自网络

翻译译者

早早

审核员

审核员EM

视频来源

https://www.youtube.com/watch?v=HeQX2HjkcNo

相关推荐