【挑战毕导】停机悖论三句话就能证明不完备性定理？

[@alxu8772]

我在中文的wiki上找到了哥德尔第一不完备定理的证明要点，我整理如下： 用到的一个重要的概念是命题形式。 哥德尔巧妙地利用了命题的“真值“为真和“含义”为真的区别，从而构造出了含义为真而真值不可证的命题，又避免了悖论的陷阱。形式逻辑系统的命题本身是没有含义的。命题只有真值而没有含义。当形式逻辑系统被实际应用时，系统中的符号都被映射到实际概念上，从而有了语义。这种映射叫做一个模型。有了模型，命题就有了含义（语义）。 公理的真值为真，但不可被证明。其它命题的真值为真当且仅当该命题可以被证明，其它命题的真值为假当且仅当该命题的否命题可以被证明。 命题形式(propositional forms)𝐹(𝑥)是含有一个自由变量𝑥的公式, 当𝑥被一个特定的数代替，它就成为一个真正的可证的特定命题。如果系统是完备的, 所有命题是在系统中要么是可证明的，要么可证伪的. 例如若𝐹(𝑥)定义为：𝑥是偶数。当𝑥=2时𝐹(𝑥)是可证明的，而𝑥=3时𝐹(𝑥)是可证伪的。 任何命题形式𝐹(𝑥) 有一个哥德尔数𝑮(𝐹), 命题形式𝐹(𝑥)的哥德尔数𝑮(𝐹)与自变量𝑥无关. 命题形式不可自证的定义： 命题形式𝐹(𝑥)是不可自证的,当且仅当命题𝐹(𝑮(𝐹)) 是不能被证明为真的. 定义命题形式U(𝑧): 哥德尔数为𝑧的命题形式𝐹(𝑥)是不可自证的. 定义命题: 𝑝=U(𝑮(U)) 这个命题可以翻译成: 哥德尔数为𝑮(U)的命题形式U (z)是不可自证的. 也就是命题U(𝑮(U)) 是不能被证明为真的. 如果𝑝是能被证明为真的，于是命题𝑈(𝑮(𝑈))为真，根据U(𝑧): 的定义，𝑧 =𝑮(𝑈)是某个不可自证命题形式的哥德尔数。于是𝑈就是不可自证的，根据不可自证的定义，𝑈(𝑮(𝑈))是不能被证明为真的。这一矛盾说明𝑝是不能被证明为真的。 如果𝑝是能被证明为假的，命题𝑈(𝑮(𝑈))为假，根据U(𝑧): 的定义，𝑧 = 𝑮(𝑈)就不是不可自证命题形式的哥德尔数。这意味着𝑈不是不可自证的。根据不可自证的定义，可知𝑈(𝑮(𝑈))是可被证明为真的，推出矛盾。这说𝑝是不能被证明为假的。 通过以上两方面的证明，证实了𝑝是不能被证明的。这也就是𝑝的含义。 所以𝑝的含义为真，但𝑝的真值不可证。 哥德尔的原始证明可能更复杂，也更严格。暂时没时间去研究。 先说一下我自己的思考。 1. 是否允许定义命题形式U(𝑧)？ 如果在所研究的公理体系中不允许定义命题形式U(𝑧)，那整个证明就没有意义。 一个命题形式只要用数字代入变量能形成一个命题，不管该命题是否为真，这个命题形式就是可以定义的。 命题形式U(𝑧)当z用某个命题形式𝐹(𝑥)的哥德尔数𝑮(𝐹)代入是形成的命题是 “命题𝐹(𝑮(𝐹)) 是无法证明的”. 首先“命题𝐹(𝑮(𝐹)) 是无法证明的”是一个命题，𝐹(𝑮(𝐹))也是一个命题，在公理体系完备的假设下，𝐹(𝑮(𝐹))是可以证明或证伪的， 也就是“命题𝐹(𝑮(𝐹)) 是无法证明的”是伪命题。 也就是命题形式U(𝑧)中z代入一个命题形式的哥德尔数，能形成的一个命题，并且命题是伪命题。 所以允许定义命题形式U(𝑧)。 2. 命题形式U(𝑧)中的z代入一个数值是否形成一个命题？ 这里就涉及到什么是命题的定义了。命题是一个判断性的语句。 命题形式U(𝑧)中的z代入一个数值是否形成一个命题就要看，代入后是否形成一个判断性的语句。代入后的语句是 “哥德尔数为𝑧的命题形式𝐹(𝑥)是不可自证的”。 如果z是一个命题形式𝐹(𝑥)的哥德尔数。那么“命题形式𝐹(𝑥) 是不可自证的”是一个命题。 如果有些数不是某个命题形式的哥德尔数，那么这些数对命题形式U(𝑧)是无效输入。这就像函数有之间的有效域一样，命题形式U(𝑧)也只接受有效输入。 3. z=𝑮(U)是命题形式U(𝑧)的有效输入吗？ 是. 因为z=𝑮(U)是命题形式U(𝑧)的哥德尔数。 4. p=U(𝑮(U)) 是一个命题吗？ 是，这个命题等价于：“命题形式U (z)是不可自证的”， 也等价于“命题U(𝑮(U))是不能被证明为真的” 这就出现了一个命题说自己是不能被证明为真的 。 U(𝑮(U)) 是一个命题，同时也是不能被证明为真的。

[@BilePeng]

这个号牛逼，挖到宝贝了……

[@lyngkplayer3037]

当年学完计算理论后，我的感受不是“存在不能证明的问题” ，而是“几乎所有的问题都不能证明”。因为有不可数个不同的形式语言（即字符串的子集），却只有可数无穷多个图灵机。 就像“几乎所有的实数都是无理数”一样，“几乎所有的语言”都是不可判定的😅

[@mejianLM]

跟病態函數以及無理數占多數一樣反直覺但數學上正確

[@我的訴求就是121個訂閱]

@@mejianLM病態函數？

[@mejianLM]

@@我的訴求就是121個訂閱 像是無處不連續但處處不可微的函數

[@我的訴求就是121個訂閱]

@@mejianLM 喔喔，魏爾斯特拉斯函式😅

[@mejianLM]

@@我的訴求就是121個訂閱 不只一種 但這是最早的

[@kexu6915]

你要这么说我还能发明个能有限字符串大小编写出的自输入真假判断机X(a)不存在定理。 1.有一类有限程序A(m)，以字符串m为输入，然后可以输出真T或假F。然后有一类自输入有限程序A_S()=A(a)，a就是编写A的字符串。这个A_S()肯定是存在的，函数A(m)可以以任何字符串为输入，以自己编写函数A(m)的字符串为输入完全没问题。 2.假设有一种有限字符串大小编写出的自输入真假判断机X(a)，它总能正确判断出A_S()=A(a)的输出是T还是F。 3.构造一个反转有限程序M(a)=R(X(a)),R的作用是取反，就是T变F，F变T。显然M也是有限字符串大小编写的，记为m。 那么bug就来了： 对M输入m的字符串，那M(m)=R(X(m))=R(M_S())=R(M(m))。我等于我的取反。 所以X(m)无论判断是T还是F都不行，所以万能有限字符串大小编写出的自输入真假判断机X(a)不存在。 所以宇宙里的电脑永远无法完美预测出宇宙每个粒子的运动，因为宇宙包含它自己了。 我想了下这里要求X(a)不能依靠执行一遍A_S()来判断A_S()的结果，只能通过别的分析，因为后面有自我指涉，通过执行一遍来判断的话会无限循环。 比如通过执行一遍来判断的话就是X(a) =call A_S()，放入自身的话就会一直call M(m)这个程序不会停止。那就是书里的人拿着本书的效果。 所以准确来说是不存在不通过执行一遍而只进行其它分析就能判断出一个自输入程序的输出为真假的程序。 有点理解图灵为啥要以是否停机来作为标准了。

[@tongjunhui8420]

其实相比于“我是不可证明的”这种直接的自我指涉，哥德尔不完备定理的证明相当于构造了以下的间接自我指涉： 替换句子"替换句子x中所有的'x'为这个句子的引号形式后得到的结果是不可证明的"中所有的'x'为这个句子的引号形式后得到的结果是不可证明的。 这个句子从“是不可证明的”前面的部分恰好展开成了它本身。于是它等价于说，它本身是不可证明的。 （注： 替换句子x中所有的'x'为这个句子的引号形式后得到的结果 -- 这句对应于主流证明中的diag对角化） UP主最后的问题，把程序本身给自己作为输入，也是可以的。这类似于打印自身的程序Quine, 是完全可以写出来的。但是都依赖对引号的间接引用（因为输出一般是用一个引起来的字符串），我想也是因为这一点才达成了间接的自我指涉罢。

[@Wind_of_Night]

我記得有句話，可以直轉換成一個大家所熟悉的哲學問題。 〝全知全能的神，能不能創造一個他舉不起來的石頭〞 這句話在學術界，尤其數學界，命題解釋與討論就很好笑，在哲學議題也是。

[@alantang4340]

其實這哲學問題在中世紀已經被反駁了，現代哲學家不會用這來問題來證明上帝不存在😅

[@jefflnuyasha]

原本我想打個1000字長文來解析"全知全能的神"這個問題，不過看到樓上回覆我就想想算了。基本上就是這個問題挺不怎樣的很好解(雞生蛋問題也很好解)。

[@Wind_of_Night]

@@jefflnuyasha 文字長不見得好，就跟論文一樣，重點在於結論。其他的東西只是在佐證自己的觀點而已。

[@德尼]

理髮師可以先為自己剪一次髮, 然行就再也不能幫自己剪髮: 解, 理髮係一個完整過程, 如10分鐘完成後, 先叫理髮, 那麼, 在10分鐘前,理髮師從來都未為自己理髮,所以可以進行理髮, 在10分鐘後,理髮已完成, 所以理髮師己為自己理髮, 以後再也不能為自己理髮. if(object.selfhaircuttime = 0) Haircut(object); Else break; Function Haircut(object){ Object.selfhaircuttime +=1;}

[@U7871]

这种自我指涉带来的矛盾，归根结底，是因为我们的语言，数学的逻辑，图灵机的计算 ，他们的数量，都没有超越一个整数的范畴，是可数无穷的，所以，他们自己都可以变成自己处理的对象 这句话怎么理解： 自我指涉问题： 自我指涉（self-reference）是指系统或表达式在某种程度上引用自身的情况。例如，语言可以描述语言本身，数学命题可以包含关于其他数学命题的断言，图灵机可以模拟其他图灵机（包括自身）。 自我指涉常常会引发悖论，比如著名的罗素悖论（Russell's Paradox）和理查德悖论（Richard's Paradox）。这些悖论揭示了在自我指涉情况下系统可能会陷入矛盾。 可数无穷： “整数的范畴”和“可数无穷”是数学概念。整数集合是可数无穷的，因为我们可以给它们编号：1, 2, 3, ... 语言、数学逻辑和图灵机的计算所能处理的信息量也是可数的，即便它们是无穷的，但仍然是可数无穷。这意味着我们可以给每个可能的表达式、命题或计算步骤编号。 处理自身的对象： 因为语言、数学和计算是可数的，它们可以描述和处理自身。例如，数学逻辑可以研究数学系统的性质（元数学），图灵机可以模拟其他图灵机（元计算），语言可以描述自身的语法规则（元语言）。 这种自我处理的能力使得它们能够成为自身的对象，但也因此带来了矛盾和悖论的可能性。 总的来说，这句话的意思是因为语言、数学逻辑和图灵机的计算都属于可数无穷的范畴，它们具有自我描述和处理自身的能力。这种能力虽然强大，但也引发了自我指涉的矛盾和悖论问题。

[@ab1053897310]

在a very short introduction to logic中看過類似的解法

[@leeneil7374]

17:16 當各個大神還在討論我完全無法理解的問題時，我只看得懂這個🥲

[@Wind_of_Night]

在另一個描述系統中，恆定持續移動，可以視為靜止不動。 因為當你身在恆定移動的系統中，你感覺不到任何加速度，如果你沒有參考系統作依據，你根本不知道你自身的初始出速度。

[@Weeping.F]

判断是否会停机: 我去吃顿饭, 回来还没停就是不会

[@aladdintw]

哈哈哈哈哈...

[@Chuen666]

12:09 第四行是不是有點小問題 n/2會是float（浮點數） 再放到range()裡會報錯吧？

[@stephenliao63]

find = False for a in range(2,2): # ??? … if not find: break # break at the first iteration

[@alxu8772]

用停机问题确实可以证明哥德尔第一不完备定理. 但视频里有不严谨的地方. 最重要的是对图灵机的定义. 视频里有时把图灵机的程序称为图灵机, 有时图灵机是指程序和输入. 用程序表示图灵机所有状态和规则, 以及表头的初始状态. 而把纸带的初始状态叫做输入. 一个程序和一个输入唯一确定一个图灵机, 用 M_i=M(C_i,X_i) 表示, C_i 是一个程序, X_i是C_i能接受的一个输入, M_i 是由C_i和X_i 确定的图灵机 这样可以证明 "不存在一个程序可以在有限步内确定任意一个图灵机是否会停机". 证明方法就是视频里讲的反证法, 先假设存在一个程序K, 可以在有限步内确定任何一个图灵机是否会停机. 程序K的输入是图灵机. 再定义一个新的程序Q，它的输入也是一个图灵机X，而程序Q的规则是，如果用程序K判定图灵机X会停机，就进入一个无限循环状态。如果用程序K判定图灵机X不会停机，那么就进入停机状态。 现在定义一个新的图灵机Z， 它的程序是Q，而输入是图灵机Z，Z=M(Q,Z)。这里图灵机Z是自己的输入图灵机， 有自我指涉， 所以Z是一个无限嵌套 Z=M(Q,M(Q,M(Q,M(Q,M(Q,....))))). 虽然Z=M(Q,Z)中左边的Z比右边的Z多一层嵌套，但右边的Z是无穷层嵌套， 再加一层也还是无穷层嵌套。所以左边的Z和右边的Z是一样的。 现在用程序K来判断图灵机Z， 图灵机Z会停机吗？ 假设Z会停机，那么根据程序Q的规则，会进入无限循环状态，也就是Z不会停机。 假设Z不会停机，那么程序K在有限步内能判定Z不会停机，根据程序Q的规则，Z会停下来。 以上矛盾表明 "不存在一个程序可以在有限步内确定任意一个图灵机是否会停机"。 后面用"不存在一个程序可以在有限步内确定任意一个图灵机是否会停机"来证明“存在无法证明的真命题”的方法跟视频里讲的一样。 如果“不存在无法证明的真命题”或者说“所有命题都可以证明或证伪”， 也就是说每个命题都有存在一个证明或证伪的过程，这个过程有一个哥德尔数。这样对任意一个命题，只要逐个检查自然数为哥德尔数的语句是否证明或证伪这个命题， 就可以（在有限步内）证明或证伪这个命题。 而一个图灵机会停机也是个命题，也可以在有限步内证明或证伪。也就是可以在有限步内确定任意图灵机是否停机。 这与前面证明的"不存在一个程序可以在有限步内确定任意一个图灵机是否会停机"矛盾。 这也就证明了"存在无法证明的真命题" 这个证明最关键的地方就是定义图灵机Z，它的程序是Q，而输入是图灵机Z本身。这个图灵机是以Q为程序的无限嵌套，并且没有除程序Q之外的其他输入。是否允许有这样一个图灵机存在，是这个证明是否成立的关键。

[@alxu8772]

@manshi_math，@snaker90 ，@edgewilliams138 几位看看我上面在视频里讲述的内容基础上改进的证明是否有漏洞

[@liudan489]

本质就是任何逻辑系统里面，只要所有的数学描述元素都是对等的，那么就无法解决主观视角带来的自指悖论，要解决这个问题，必须引入上帝视角，那么上帝视角又会带来高层次的世界系统，这样就无限嵌套下去了，所以，所有的世界其实都是无法独立存在的，我们其实在层层嵌套的数学构造世界之中。

[@logic0000]

11:56可是这个这种程序只能一步一步搜索，也就是说通过这种方法解决的数学问题搜索空间必须是可数的无限。如果一个数学问题的搜索空间是不可数的无限，要怎么转换成代码停机问题来证明呢?

[@eoc8a68o9]

高智商低情商系列 😂+1

[@我的訴求就是121個訂閱]

真的，up很酸人的😅😏

[@snaker90]

14:10 的反证法存在非常低级的错误，应该是你自创的吧？ 你定义了一个所谓的 M’ 图灵机，它可以用于判断任何类型的图灵机。也就是说，M’ 需要输入内容才能运行。 这意味着「M’ 并不是一个图灵机」，因为 M' 自身缺少处理内容 (也就是"纸带")，它无法像正常的图灵机那样独立运行。 所以, 当你将 M’ 自身输入到 M’ 中时，是在将一个「非图灵机」输入到了 M’ 中。这在编程中称为 “参数类型不符”，是会报错的。

[@alxu8772]

这也是我提出的问题，纸带是不是图灵机的一部分？ 两个具有相同规则，相同表头初始状态，但不同纸带的图灵机是不是相同的图灵机。 如果算是相同的图灵机，那么视频的问题就是把3类图灵机（1.一定会停，2.一定不会停，3.输入某些纸带会停，其他纸带不会停）硬要分成两类。 如果不算是相同的图灵机，那么视频的问题就是把不同的图灵机当做相同的图灵机，从而引起的矛盾。 总之都是用自己错误的理解来证明，那顿火锅是骗来的。

[@manshi_math]

视频讲的可能不太清楚，但这个证明是没有问题的，我的确跳过了“还需要有纸带作为输入”这一部分。严格来说，这个M应该是接受代码C和输入X，判断M(C, X)会不会停机。而kleene定理保证了，我们可以找到一个M'，并且它在计算M(M', M')

[@snaker90]

视频作者你好, 你的反证法错误在于你的基本定义是错误的. 你回复的 "M(C, X)" 和 "M(M', M')" 都犯了这个错误, 错误共有两点, 以下是详细说明: 一. M(C, X) 应该写成 M(C) 对于 M 来说, "代码C" 就是要输入到 M 中的内容，因此 "代码C" 跟 "输入X" 是一回事. 你不应该分成两个变量来写. 也就是说 M(C, X) 这种格式中的 X 是多余的, 你应该直接用 M(C) 来表示一个图灵机. M(C)表示 "M + 代码C" 组合而成的图灵机. 如果输入的是代码D，就应该写成 "M(D)". 需要注意的是, M(C) 和 M(D) 都是图灵机, 但不是同一个图灵机. 因为两者的"纸带"不同, 输出结果也可以是不同的. 因此, 你在回复中提到的 M(M', M') 实际上应该写成 M(M'). 但即使写成 M(M') 它仍然是错误的. 这是因为第二个错误. 二. M(C)是有效的图灵机, 但 M(M')不是 根据你视频的定义, 输入到 M 中的东西必须是一个图灵机. 代码 C 之所以能输入到 M 中, 是因为代码 C 等价于一个图灵机, 因此 M(C) 是有效的. 但 M(M) 是无效的. 因为 M(M) 括号中的 M 并不是一个图灵机. M 只有与图灵机等价物 (例如代码 C) 组合后, 才能作为图灵机输入到 M 中，例如 M(M(C)), M(M(D)). 你所定义的 M(M') 跟 M(M) 是一样的, 都是一种无效定义, 原因是一样的: 括号内的对象并不是图灵机. 以上就是你在基本定义上犯的两个错误, 第一点是次要的, 第二点是主要的.@@manshi_math

[@alxu8772]

@@snaker90 我认为把图灵机定义成由代码和输入两部分组成并没有什么问题。只是当把另一个图灵机当作输入的时候，另一个图灵机的代码和输入一起作为输入。可以定义图灵机为M(C,X), C 是代码， X是输入。 当把另一个图灵机当输入是， X=M(C',X'), 处理图灵机的图灵机就成了 M(C,M(C',X'))， 这里M(C',X')是输入的图灵机。M只是图灵机的统称，M(C,X)才是一个具体的图灵机。 如果一个图灵机以自己作为输入， 就变成了 M(C, M(C,M(C,M(C,M(C,....)))). 因为有自我指涉，所以形成了一个无穷嵌套。如果用Y 来代表这个无穷嵌套的图灵机， 那么Y=M(C,Y)。

[@TeslaNicola-m3s]

M'输入的内容不就是M'本身？

[@Jake_kumar]

12:33 就是reduction 吗 大学各种证明np题

[@aaw4519]

這就是死去的演算法開始攻擊我嗎

[@eugeneL_N1E104]

reduction is from known to unknown?

[@YuN_0705]

可數無窮多有點浮誇

[@四步道君]

可以认为停机问题等价于就是寻找满足存在数ε使得，任意大于ε的数ζ令递推数列递推ζ次始终收敛到有限集合的充分必要条件吗？

[@哈里-x6i]

問，所以語言的可數無窮性質跟自我指涉的存在有什麼關係？就算不可數無窮也會存在這種命題吧？

[@FoD-og4oz]

Langton的蚂蚁让我想到，难道这个世界一开始的也是不确定、再到无限循环可确定的吗？

[@FlAsChang]

12:13 代碼跟圖靈機的狀態是如何對應的 太神奇了吧

[@蔡秉諺-f5g]

這世界上可能有一個原始的圖靈機，他叫RNA

[@耗子尾汁马保国]

18:37 考场的时间限制就是防止你用图灵机吧😅

[@despirdzhang3225]

你在用一个更高的demo成本来demo一个比毕导的sub(n,n,17)更简单的不完备性证明，而且你们两个比李永乐的demo成本都高，他只有黑板和粉笔😁

[@hypatia-du-bois-marie]

三句話? 一句話! □(□⟂ → ⟂) → □⟂, 第二不完備性得證! (*當然 technically 沒這麼簡單 (元數學有力量! lol 18:14 其實 true 可以被證明, provable 能夠被證明, 這兩個翻譯比較奇怪... true but not provable 你會說成是「可以被證明但不能被證明」...

[@user-user-user-user-user-888]

如果算命師算到自己說自己會死 因此能活下來 所以說自己會死 然後活下來了 這樣仍代表他會算命

[@LeiurusQuinquestriatus]

可能是躲不掉的劫難還是什麼的

[@fuctin5954]

只用三句话，那是因为视频里面直接把“哥德尔数编码命题”拿来用了。

[@brianmak2501]

想起一句話：以有涯隨無涯，殆矣

[@bradfordsalviejo8711]

你这个视频的内容在真理元素的视频里已经讲过了

[@shanpoyang]

第请问10分钟的那个图灵机叫什么，我暂时还没明白这个的规则，想查找一下资料了解一下

[@edisonhello2012]

可以查一下 Busy beaver

[@Mr0Eminal]

在中国你能预知未来也不可能中彩票

[@Enderwarrior]

-因為預知的未來是那個不是你-

[@HJ-wt1ql]

穿越者可以用这条定理证明是否处在中国

[@莱蛙超进化核蛙]

那只是你不能而已.

[@doutu4624]

不需要预知未来也可以100%中彩票

[@fireandcandy]

可能我比較無知且樂觀： 波學說明萬物皆可以是一種波，而傳統（牛頓）力學在證明時沒有考慮到物質波動性。 但這不影響我們對於傳統物理學的追求。

[@zhao3415]

但還是影響了我們被傳統物理學侷限，面對部分客觀存在的物理現象（比方更宏觀、更微觀的物理現象）束手無策呀 😂

[@zhao3415]

漫士沉思錄還有另一期影片對我啟發很大，很推薦您也看看！在談所有自然數的總合為什麼真的有可能是-1/12。至於這為什麼跟現在的話題有關……說明起來太複雜了，還是直接看漫士的介紹細品好了 😂

[@SadGuypeeloudest]

5:32 噔噔咚（心臟驟停）

[@NightSickle]

15:24 雖然我理解這只是拿來比喻，但是其實那比喻和前面提出的圖靈機不一樣，因為人類可以說謊，它可以為了活下來而講反話，帶回圖靈機來解釋就是他多了個條件：不管結果如何，他都能按照自己的心情給出結果，結果就是無論循環還是停機都無法得出任何證明，所以用那個問題來證明世上沒有人會算命是不成立的

[@hanwang114]

这三句话我还是不明白。K师傅可以尝试用枚举法开F里所有的锁；只要F里锁本身是好的，就能打开；停机问题这把锁是F中一把坏锁，K师傅打不开。 这哪里有矛盾呢？

[@LinYuanXianYu]

字幕錯了 自我指涉打成自我指示了

[@特別的特特special_TT]

15:23 不是沒有人會算命，是沒有人能算出自己所在的宇宙中發生的事情，因為當一個人算出了自己所在的宇宙中所發生的事，那麼他就會依照該結果去改變他的行為，除非他在未來的任何舉止都沒有受到該結果的影響，但是那是不可能的，除非他將自己的記憶清除，但是這樣就失去了算命的意義，四捨五入就等於沒人能算命。 但是如果一個智慧體或者電腦等能夠進行運算的實體不處在我們的世界上，或是更準確地說，該實體並沒有辦法或是控制可以自身不與其進行運算的物體產生任何交互，並不會因為該結果而去改變進行計算的物體在未來發生的事，就比如說看過一部電影之後，如果將劇情記下來，那麼就能進行預判，但是這沒有太大的意義，只會被當作暴雷仔。 總而言之，不是沒有人會算命，而是沒辦法運算出準確的結果並且達成我們算命的目的。

[@matches20]

無限/無限= 根號 無限^2=

[@CuteAkiyamaMizuki]

万能的上帝能不能造出一个万能的上帝搬不起的石头

[@user-bk3zt8sp1dfnodes]

真空的球形雞: 彈性碰撞、動量守恆? 圖靈機( linked list ? 圖靈完備。 ): 計算的本質和能力的極限?

[@ouo9454]

CPU燒了就會停機😂

[@dk_wholesale]

開啟 一下 Thanks 功能哈...

[@CarbonDioxide-g9z]

17:17 什么数字飘过去了😂

[@liujian012]

标题太不贴切。我听了三十多句，也没弄明白图灵机到底是个什么东西。又看了一眼进度条，发现事情没有那么简单。

[@superyngo]

狀態就是input+code 紙條就是memory+output 我看完的理解是這樣

[@SamDaBest]

@@superyngo 不算是 input 是寫在紙帶上的 然後會有一個指針指著紙帶上的格子 指針可以向左右移動或修改格子裡面的內容 state 是紙帶在程式執行的每個時間點的樣子 memory 則是紙帶的長度沒錯 不過理論上通常會 assume 是無限長的 code 是描述指針的行為 當圖靈機執行完畢後 會把 output 寫在紙帶上 但簡單來說 平常會使用的程式語言、電腦 都是可以模擬圖靈機的行為的 所以除了理論方面以外 把圖靈機當成是一台電腦就好

[@darwangpie-whatlieshionsha4168]

评论区里smart ass还挺多，不知道他们是听懂了，还是没听懂。

[@Xiao0616]

好24分鐘過去了，我沒有一句話聽的懂。

[@莱蛙超进化核蛙]

听了三人至二,感觉就是无穷算力去追求无限一样.判断停机就是判断真假,判断永恒,判断毁灭,判断湮灭!以至于无穷的事.说白了就是一个从无限里找通用解罢了.我一句话就说清楚了.

[@wei-jyunsun8222]

沒想到能在高談理論的殿堂看到野獸先輩.........

[@user-user-user-user-user-888]

如果他預知未來 只預知到他沒有暴富的結果呢

[@alxu8772]

认证看完了你的视频。还是觉得有问题。 首先，你是把图灵机分为会停和不会停两类吗？ 那么一个图灵机遇到某种情况停机，其他情况无限循环, 这种图灵机属于哪一类呢？ 所以你的分类是有问题的，你并没有把所有图灵机分成两个不重叠，又无遗漏的子集， 虽然“会停”和“不会停”听起来像是这样的两个子集。 看起来像是由语言不精确引起的问题。 我来试图重新分类。 第一类是（不管遇到什么情况）最终一定会停下来的图灵机。 第二类是有可能不停的图灵机。 注意第二类的图灵机也有可能停下来，但并不是能停下来的图灵机都属于第一类。 也可以说是对图灵机的定义的问题。如果两个图灵机有相同规则，和不同的初始状态，是否算做同一个图灵机？还有图灵机处理的对象（输入）是不是图灵机的一部分？

[@user-xj2yv7uk6h]

圖靈機停機問題是包含圖靈機、初始狀態和狀態集的，所以不同初始狀態的圖靈機停機問題不一定有相同解，除非兩者會走到同一狀態

[@alxu8772]

@@user-xj2yv7uk6h 我的问题是怎么定义一个图灵机。 跟图灵机相关的有3个部分。1.规则， 2.表头状态，3.纸带。 相同规则，相同表头初始狀態，但有不同初始纸带的两个图灵机是否算作相同图灵机？也就是定义一个图灵机是否包括纸带初始状态。 如果定义一个图灵机包括规则和表头初始状态和纸带的初始状态, 那么一个图灵机只能处理一个问题。这种定义下，那么按是否会停来分类，图灵机可以分为2类, 会停和不会停。这这种定义下，视频的问题是把不同的图灵机当作相同的图灵机。 如过定义一个图灵机，包括规则和表头初始状态，但不包括纸带的初始状态。 只有这样定义，才会出现视频中所说的矛盾。 但如果是这样定义，那么按是否会停来分类，图灵机可以分为3类，1.不管什么纸带，一定会停。 2.不管什么纸带，一定不会停。3. 碰到某些纸带会停，而碰到另一些纸带不会停。 视频里硬要把3类图灵机分成两类，当然会出问题。 两种定义下，都是用自己不正确的理解来证明命题。那么这个证明是不能被接受的。

[@alxu8772]

简单来说，一般情况下一个命题的真值要么为真，要么为假。只有“真”，“假”两种值。但总可以构造出一个命题，它的真值既不是真，也不是假。 那它的真值是什么呢？ 佛曰：不可说，不可说。（佛教早提出了哥德尔第一不完备定理）

[@kyant7529]

真值不确定的就不叫命题了，叫作断言

[@NightSickle]

你提出的問題本來就是偽命題，你定了命題一定有真假，卻說非真非假，推翻了前提，不能用一個錯誤的前提去提問，打個比喻就是有人問你婚禮辦在什麼時候，前提已經確定你有要辦婚禮了，畢竟這題是問你什麼時候辦，不是問你要不要辦，所以如果你沒有要辦婚禮，那你根本回答不出這問題，而“沒有要辦”這回答並不是這問題的答案範圍內（但人類可以用這回答來進行溝通，可見人類的思考是非常複雜的）

[@NightSickle]

如果要按照你的前提，那麼和影片裡提到那樣，只要自證就能夠出現你想要的答案了，即：“這個命題答案為假”

[@tenderice42]

折腾一大圈，其实远不如 sub（n,n,17）严谨和简洁，漏洞太多，根本没有理解 GIT 的本质

[@alxu8772]

我看到的sub(n,n,17)一点也不严谨，甚至是错误理解（至少我认为是这样）。如果你看到过严谨的sub(n,n,17)证明，请给个链接

[@tenderice42]

@@alxu8772 可以买一本数理逻辑教科书去看，里面一般都会有完整证明过程。客观说，大部分证明过程也不是 100%严谨，因为会把一些约定俗成的推理过程简化掉。这方面我看过的最严谨的是汪芳庭的《数理逻辑》，里面每一句都是严格的。不过这也是早期的一本教科书，后来改版之后的我没看过。不确定是否一字不差

[@alxu8772]

@@tenderice42 我不是要找一个严谨的证明，而是要找一个用sub(a,b,c)来实现的严谨的证明。不知道你说的汪芳庭的《数理逻辑》是不是用sub(a,b,c)来证明的。

[@tenderice42]

@@alxu8772 看来你不是太了解哥德尔不完全性定理。所谓sub(n,n,17)或者sub(n,17,n)这类形式的证明，就是指的哥德尔给出的原始证明。这个证明是基于一阶算术理论给出的一种“初等证明”，是纯数学的，基于“哥德尔数”这个伟大创造，这也是哥德尔的最大贡献。其他类型的证明，都依赖于模型论、元数学理论等基础，虽然也是“正确的”，但是并不符合“真正从数学当中构造出一个具有自我指代属性的不可证明命题”的原始动机。汪芳庭的《数理逻辑》是我见过的对这个原始证明最详细的描述，因为哥德尔本人的论文和其他一些介绍者的文章，都有大量的省略或者隐含的前提假设，可能因此导致你没有看明白。所以如果你找到汪芳庭的书来看，应该能真正理解sub(n,n,17)的推理过程。

[@tenderice42]

@@alxu8772 如果你想找一个简化的版本，上面这个链接是我看到过的最简单清晰的版本了。如果你发现里面还有一些省略内容或者隐含假设，导致你不理解或者不认同的话，那你只能去看数理逻辑教科书了。

[@hlz657]

up主思考能力不错 但人外有人 提示你一下 康托尔对于自然数的定义是错的 以及你所有take for granted的底层逻辑都是错觉 如果你能质疑所有底层belief 并找到答案 就能发现究竟的真理 up的思考很深 但不究竟 图灵机也不是最本质的模型 它只是个表象的模型 所以基于图灵机推导出的一切 都无法触及本质or究竟真理 一切都是根深蒂固的错觉 包括被奉为圭臬的数学

[@會寫程式的羊]

13:47 舉例不夠嚴謹 因為人做甚麼是個人的選擇，可能只代表他沒有想到或沒有這樣做

[@雨楓-u4q]

這部片子也解釋了何謂修行，人對於未來是無法確定的，因為要實際跑過才知道，又因為人類會恐懼未知，所以你必須把自己的這程序自己修訂內心代碼到不動的情況，就能面對未知的恐懼了

[@Ben-u8w]

代码可以发吗

[@yiacov]

“吴京手里的大窑上面有没有吴京？“

[@efaye0224]

那個螞蟻的規則裡就沒有停下來要怎麼才會停下來？

[@黃聰賢-b4w]

那一題的問題是螞蟻會不會離去無窮遠，所以問題其實應該理解成螞蟻會不會循環。那只要全局變數出現重複，就算是確認循環發生了。螞蟻的狀態+地板狀態剛好與之前某次完全相同，那就可以確定螞蟻只能在有限的軌道上持續循環，不會跑向無窮遠處

[@chow4444]

靠腰原來是數學啊

[@Dumm11111]

一頭霧水

[@LatticeMage]

好猛

[@zhengfang3619]

话说猜想和图灵机转化的关系有机会来一段吗

[@wk7231]

17:13 怎麼在這麼複雜的課堂裡有一個濃厚的臭味啊

[@ZHENG1990]

密碼鎖怎麼開 就試阿

[@wk7231]

@@ZHENG1990 不是 114514查一下

[@BoZhong-j7u]

感觉可以这么证明这个contradiction因为是boolean。 M'（M'（M）） = M‘^{-1} \Rightarrow M'(M'(M'(M)) = 1. Thus M'(M) = 1. qed ：）

[@peterwan816]

這個不就是像理髮店悖論，不是說了這樣的定義是不可以的嗎？

[@我的訴求就是121個訂閱]

不一樣⋯⋯⋯

[@TeslaNicola-m3s]

那是zfc修正，一种替代方案，也就是将朴素集合论进行了限制，而这个问题不受这个限制，因为这个问题考虑的是一个更通用的解法，而不是在zfc公理体系内的问题。

[@user-bob-pikachu]

關於停機問題很多漏講，要先說明任何代碼是可數無窮的，停機問題無法透過圖靈機器解決，但不代表其他計算機無法解決停機問題，只要這個計算機比圖靈機器強就有機會

[@lambdA-qr2hr]

这里他省略了一些步骤，这个证明过程是在说明“计算模型不能模拟等价的计算模型”这个事实。

[@liyue9705]

作为程序员，我有个想法，我们为什么不约定一个数字为最大数，这样就可以取消数学里面得无限概念。这个数字只要足够大，就可以解决实际得一切问题。而且宇宙本来就有可观测范围，就不是无限大得。然后基于这个最大数，我们重新推理一套数学，并可以解决一切驳论、实现可数数学得完备性

[@fochen4573]

但這個最大數要是一個符號嗎 那就要去定義這個符號 就會回到原本無限的問題 當人類意識到無限這個概念的時候 就沒辦法去抹除無限了

[@narkewoody]

那你约定哪个数？ 然后你证明一下不存在比这个数大的数

[@carloseli7933]

有没有一种可能 有一个熟悉叫做正无穷？

[@我的訴求就是121個訂閱]

數學就是因為「無窮」，才變得有研究性，只考慮有限情況的話，那不是數學（或至少能被輕易窮舉完的）

[@kyant7529]

无穷大不是一个确定的数​@@carloseli7933

[@海綿綿冰]

17:15 這麼臭的停機悖論有存在的必要嗎?

[@ruiyangxu790]

所以问题出在我们的一切语言都是基于符号的，所以一定是可数无穷的。但是，如果某个人工智能，它不用符号作为自己的语言，而是用实数向量呢？那它所能理解的知识是不是就远远超过我们了，而且我们无法完全用我们的语言去理解它，因为实数是不可数无穷的…… 所以一定存在某种知识我们不理解，但是我们制造出来的AI可以去理解，如果它具有了某种完全意义上的实数计算系统（比如量子计算机）😮

[@aitilang]

计算机表示实数时，小数位数是有限的，所以其实它所能掌握的知识总数是可数无穷的

[@ruiyangxu790]

@@aitilang 如果是量子计算机呢？每个量子比特的状态都是连续的，应该是可以构建出实数向量机的

[@魔狼]

不用那么烦，连续统假设他就懵圈 饿😂

[@narkewoody]

视频上说的停下来是指死循环还是进入Halt状态呢？

[@insight.cn7b]

停止, 这些机器都有停机状态. 就是会运动到一个状态, 叫做停止, 然后什么都不做.

[@timt8813]

17:14 怎麼會有這麼臭的密碼

[@Penspinner.Cuber.Chessplayer]

強制停機三回阿三回

[@tangtienji]

這句話是假的，， 厲害！可以把宇宙爆掉。

[@會寫程式的羊]

那個影片我有看過

[@LongLongKo]

QKV 的符號在AI的attention也出現，是考合嗎？

[@DigitalAlligator]

attention机制很早就有了，只不过当时还没有显卡和大规模的神经网络，而当时各种各样的attention的确受到图灵读写头的启发，你可以翻翻论文，有些在前言里就提了

[@annriveroad]

感覺是數學不太好的問題，有起始條件，有運動(微分)方程式，所以你確實能藉由計算得出往後的每一步，但這個方程式有沒有穩定態，有沒有通解那是看該方程式的複雜程度，有沒有人解出來了，在數學上還沒有解析解的情況下才會有所謂的不知道要跑多久才會到達一個不知道存不存在的穩定態。

[@nanoha007]

這就是20分鐘笑30分鐘嗎

[@Ben-u8w]

17:13 好臭

[@aitilang]

？

[@Ben-u8w]

@@aitilang 114514,可以去搜一下

[@hsiao704]

5:33 就已經有味道了

[@kronee1]

然後我還是不明白

[@蔡秉諺-f5g]

你這個視頻錯了，你表面上寫三句話就可以解釋不完備定理，但你實際上使用四句話解釋。 你少說一句話： 停機問題在圖靈機裡是不可判定的。 這個命題可以證明，但是可不是公理，必須寫進證明裡。

[@manshi_math]

所以这不是花了大半个视频来解释嘛😂

[@cxz0346]

急需第二集

[@刘晓平-x6x]

听着听着就完全听不懂了。

[@neilg2256]

你是B站的谁？

[@蘇維明]

同名

[@sankoo3643]

他是清华姚班的，比毕导还牛

[@xfive5423]

17:15 好臭!

[@Bingbing-y1d]

我觉得你说的没有毕导清楚

[@naoko4927]

好

[@LinArG]

17:14 臭臭的

[@xcwei2572]

我差点就取消订阅了。哇哈哈

[@akaiwon6594]

這樣的機器，也能暴力窮舉提出所有問題嗎？真、假、完備性這些定義，是公理體系本身能給出的嗎？如果我們可以接受一個現象既是波也是粒子，為什麼不能接受一句話既是實話也是謊話呢？不過，人類的邏輯當然是可以接受，不能接受的是機器和數學的邏輯。

[@leoc2844]

毕导看到你视频了吗？理你了吗？

[@vacuumisallinone2618]

謝謝