用证明停机问题的方法证明人类方法无效性

gghhjj

用证明停机问题的方法证明人类方法无效性

现在我就考虑，我们能否步证明停机问题的方法。证明这样一个命题：人不能用自己的方法来判定自己方法的有效性。这里我们定义方法的有效性是“在有限的步骤内可以解决一个输入带来的问题”。
一、用设计方法否定假设来证明。
让我们考虑这样一个问题：对于人类说，存在不存在一个方法比如说P，能够判断出任意一个方法X是否会在输入Y的情况下是有效的？我们不妨设P(X,Y)表示P判断“方法是X，数据是Y”的结果。如果存在该方法的有效性，那么P(X,Y)就输出一个“yes”。如果不存在该方法的有效性，那么P(X,Y)就输出一个“no”。我们的问题就是这样的P(X,Y)存在么？这就是模拟停机问题提出的人类方法问题。所谓的某个方法X在输入Y上“有效”就是说X在有限步骤内可以解决问题，反过来如果“无效”就是不能在有限步骤内解决问题，其实这里的“有限步骤内解决问题”和“停机问题的死循环”是一回事儿。那么，这种判断方法有效的方法P存在么？
答案是不存在的。下面我可以证明我的这个结论。
我们不妨假设方法P存在。那么我们可以根据P设计一个新的方法Q如下：（由于人类的方法是用语言表示的，我们的p也用语言来表示，但是我们模仿程序格式写）
X是任何一段方法的代表符号：
方法Q表示如下：
用m表示方法P(X,X)的结果 （即m=P(X,X)）
当方法P(X,X)输出为no时， （即do while (m=no)）
进入一个不能用有限步骤解决问题的死循环。 （即…
…
end do）
如果方法P(X,X)的结果为yes则方法Q结束。 （即if m=yes then return）
后面的程序语言纯属于停机问题证明对比。对本证明没有实际意义。
这各方法Q的通俗解释就是：输入任何一各方法X，调用判断方法P(X,X)并得到返回值m，如果m=no，也就是说根据方法P的定义，P判断出方法X有效。那么Q就进入不能用有限步骤解决问题的状态。如果m=yes，我们知道这表示P判断出程序X无效。就结束该方法Q。
我们可以看到，这样定义的方法Q(X)是没有问题的。下面就进入关键时刻了：我们问Q这个方法作用到Q自身时，也就是Q(Q)会不会有效呢？当然我们可以运用强有力的方法P(Q,Q)来解决这个问题。
假设Q(Q)会无效，那么P(Q,Q)就会返回yes。然而根据Q函数的定义，把X=Q代入其中会发现由于P(Q,Q)返回的是yes，也就是m=yes，因此Q方法会马上结束，也就是方法Q(Q)有效。然而如果假设Q(Q)无效，那么P(Q,Q)应该返回no，这样根据Q方法的定义，把X=Q代入Q(Q)之中会得到m=no，这样方法Q就会进入不能用有限步骤解决问题状态。因而Q(Q)无效！这又导致了矛盾。
显然，无论方法Q(Q)有效或无效，都会产生矛盾，然而哪里错了呢？答案只能是最开始的前提就错了，也就是说我们最开始的假设方法P(X,Y)能够判断任意方法X在输入Y的时候是否有效是错误的！也就是说这样的方法P(X,Y)不存在！

二、用对角线删除法证明。

我们仍然用反证法，假设这样的判定方法P(X,Y)是存在的。而我们知道任何方法X是可以按编码排列的。也就是可以为所有的方法进行编号：1，2，3，……，而引发解决问题的数据Y本身也可以这样编号：1，2，3，……，因而我们就可以把每一对X和Y的组合排列在一张表上。比如列表示的是数据Y，而行表示的是方法X，这样P(X,Y)的值也就是yes或no就可以写在第X行第Y列的对应位置上，表示P(X,Y)判断出的X作用在输入Y上是否无效的结果。比如下面的表就是一个示例：
1 2 3 4 5 6 …… Y ……
1 yes no no yes yes no …… yes ……
2 no no yes yes no yes …… no ……
… ……………………………………………………
X no yes no yes yes no …… yes ……
… ……………………………………………………
到这里没有发生什么毛病。我们知道上表中的每一个行都表示一个确定的程序作用到不同的数据上所得到的结果。比如程序X作用在1,2,3,4,……,Y，……上给出的结果就是一个序列：
no,yes,no,yes,yes,no,……,yes，……
下面我们把上表对角线上的元素挑出来。也就是专门找那些第1行第1列，第2行第2列，……这样的元素就可以得到一个序列：
yes,no,no,yes, ……
而根据这个序列我们完全可以构造这样一个反序列：
no,yes,yes,no, ……
也就是说这个序列在每一个位上都与前一个对角线序列不同！这个序列就称为对角线删除序列。那么我问，这个对角线删除序列是否在我们表中的某一行上呢？答案是否定的！这个序列必然不在表中。因为它的第一个元素与1,1不同，第二个元素与2,2不同，……。换一种方式解释就是：假设对角线删除序列的确在表上列出来了，那么这个序列必然在某个固定的行，比如说就在第1001行。那么我们就要考虑这第1001行，第1001列的元素，我们知道根据序列的构造方法(1001,1001)对应表中的元素是与序列上的这个元素不同的！因而产生了矛盾，也就是说这个构造出来的对角线删除序列不在表中！
我们完全可以设计出一个方法Q使得Q作用在1,2,……,X,……上产生的序列就是对角线删除序列，而对角线删除序列不在表中就意味着方法P并不能判断出程序Q作用在任意输入上是否无效。其实这里的程序Q就是前一节论证停机问题的程序Q。
用对角线删除的证明方法来看究竟哪里出错了呢？错误就出在我们假设方法P能够得到这样一张完整的表，这张表对所有的方法计算得到是否无效的答案。

证明毕。

以上证明是在张江的文章基础上修改而成，很多地方只是把程序改写成方法。
对这个证明的意义我暂时还说不清楚，但是我觉得它对突破某些什么有很大意义！

来自：研学

gghhjj

本文无意推翻对停机问题的证明。因为停机问题的证明是严格的，符合逻辑的。
人类的活动由于不会陷入无限循环，他能够在累的时候自动停下来，他能够在通过反馈机制看到活动无效时停下来。因此证明人类停机问题没有意义。
但是判断人类活动的方法无效于判断计算机停机问题却具有同样意义。这个证明的数学意义并不大，但是它的哲学意义却非常大。特别是在哥德尔定理证明形式系统的不完备性以后，不少人总是根据它的除计算机不可能超过人的结论。
本证明不过是说计算机的缺点，人类也存在，只不过不是标现在停机问题上，而是表现在对方法无效的判别上。