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

我在中文的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)) 是一个命题，同时也是不能被证明为真的。

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

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

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

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

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

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

高智商低情商系列 😂+1

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

代码可以发吗

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

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

好

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

你要这么说我还能发明个能有限字符串大小编写出的自输入真假判断机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)这个程序不会停止。那就是书里的人拿着本书的效果。 所以准确来说是不存在不通过执行一遍而只进行其它分析就能判断出一个自输入程序的输出为真假的程序。 有点理解图灵为啥要以是否停机来作为标准了。

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

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

一頭霧水

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

那個影片我有看過

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

開啟 一下 Thanks 功能哈...

急需第二集

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

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

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

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

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

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

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

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

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

CPU燒了就會停機😂

你是B站的谁？

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

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

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

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

用停机问题确实可以证明哥德尔第一不完备定理. 但视频里有不严谨的地方. 最重要的是对图灵机的定义. 视频里有时把图灵机的程序称为图灵机, 有时图灵机是指程序和输入. 用程序表示图灵机所有状态和规则, 以及表头的初始状态. 而把纸带的初始状态叫做输入. 一个程序和一个输入唯一确定一个图灵机, 用 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之外的其他输入。是否允许有这样一个图灵机存在，是这个证明是否成立的关键。

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

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

謝謝

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

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

17:13 好臭

整潔

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

然後我還是不明白

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

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