【【挑战毕导】停机悖论三句话就能证明不完备性定理?-哔哩哔哩】
网页链接看了最近另一个不完备定理的视频感觉好像弄懂了。这里用图灵机停机问题的方法来构造“subnn17”,感觉方法比毕导那里像字符串游戏一样好得多,更容易接受。也没法像上面那样构造submm17了。
我现在的理解就是可证=图灵机停机,是要优先于真假=图灵机输出的,先停机了才能输出,所以只能构造“这个命题不可证”=“这个图灵机会停机”,不能构造“这个命题是假命题”=“这个图灵机输出假”。
———————————————————
不过这个视频有个问题就是那些图灵机的输入都没有标清楚(好像还想为此再水一期视频),比如Q会停机这里就没说输入是啥,搞得我很困扰,想半天才理清楚,在这里记录一下。
第一处不可判定性的证明:
M(p,q):当p(q)停机是输出T否则输出F
M'(p):当M(p,p)停机是输出T时死循环否则停机
于是M'(M')出现矛盾
第二处不完备性的证明:
K(p):命题p可证明时输出T否则(假或不可证明)时输出F
Q(p):K(命题“图灵机p(p)会停机”)为真时死循环否则停机
于是Q(Q)出现矛盾
“p(p)会停机”就是sub(yy17)
Q(Q)则是sub(nn17)