停机问题是一个很经典的问题，而且是一个很典型的不可解决问题。
这里不讨论停机问题。
从停机问题出发，我想到了另外两个问题，不知道这里有没有人之前想过。
因为觉得很有意思，所以打算发出来大家一起讨论一下。
一，停机问题本身告诉我们：不存在一个通用的图灵机来判定任何输入的图灵机是否最终能停机。
但是，是否存在一个特制的停机判定图灵机，可以用来判定特定图灵机是否最终能停机。
比如，是否存在一个图灵机，判定“alert(1);”这段Javascript代码是否能停机？
上述代码似乎显而易见是会最终停止的。
也就是说，是否存在一个图灵机A(B)，它专门用来判断图灵机B是否会停机，对于不是图灵机B的图灵机C，如果输入A，则输出“当前图灵机不在服务区”。
所以，传统的针对经典停机问题的那种构造在这里没用，因为我的停机判定图灵机根本就对这种构造没用，我是用在指定图灵机B上的，对你的图灵机没用。
是否存在这样的专门针对B的停机判定图灵机A(B)呢？
或者，进一步说，是否可以对任意B都构造特定的判定A(B)呢？
比如，对于function(){alert(1);}，显然是可以判定的，判定为可停机；对于function(){while(1=1){}}则显然可以判定为不可停机。那，是否对任意图灵机都能构造这样的判定呢？
和经典图灵机的区别，就在于这种图灵机，换一个B就不能用了，它只适配于B。
二，是否存在一种图灵机A，对于任意图灵机B（这次不是特指的了）都能做出以下五类判定：
1，图灵机B的中间状态将指向B自身；
2，图灵机B的中间状态将指向判定图灵机A；
3，图灵机B的中间状态将指向B自身以及判定图灵机A；
3，不是1、2、3且能停机；
4，不是1、2、3且不能停机。
也就是说，对于任意输入到A中的图灵机B，A的输出状态为上述五者之一。
那么，是否存在如上的图灵机呢？
比如，停机问题中，基本上的思路是构造一个图灵机M是要调用判定图灵机P的，从而构造出类似罗素悖论的自指悖论结构。
但是，对于上述图灵机A，这种构造没用，因为如果构造一个M需要调用A，则输出2；如果构造M是调用M自己来构造悖论的，则输出1；如果M既调用M又调用A，则输出3——而对于所有别的图灵机，要么输出3要么输出4。
也就是说，对于任意图灵机，要么输出“纠结”，要么输出“可停”，要么输出“不可停”。
因而，是否存在这样的图灵机A？
对于一，如果对于任意B都可以构造判定A(B)，那么我们可以做这样的事情：
对于希尔伯特23个问题中的某个问题，写一个验证程序B，然后针对B写一个专用停机判定程序A，于是看A(B)的结果，如果结果为可停机，那么该“希尔伯特23个问题之一” 就有了肯定的答案；如果结果为不可停机，那么该问题就有了否定的结论。
而对于二，也可以做这样的事情：
写一个希尔伯特23个问题之一的验证程序B，然后输入到二所说的判定图灵机A，那么结果就可能为：
1，该问题有肯定答案；
2，该问题有否定答案；
3，该问题指向验证手法（也就是验证程序B）；
4，该问题指向判定方法（也就是判定程序A）；
5，该问题既指向验证手法也指向判定手法。
所以，如果上述两种停机判定图灵机是可以存在的，那将非常有意义。
2011-4-23 0:09:48追加一些内容：
利用第一类停机判定图灵机A(B)（也就是指针对于特定B才能进行停机判定的图灵机A） ，可以将任意图灵机分为两类：1，可被判定是否能停机的（停机可判定图灵机）；2，不能被判定是否能停机（停机不可判定图灵机）。
比如说，对于简单代码，经验老道的程序员不用编译，看看就能知道是否存在死循环，从而是停机可判定的。当然，对于复杂程序，是否是停机可判定的实在不好说，至少一般程序员估计如果不跑下程序光用肉眼看是看不出来的（至少我看不出来）。因而，对于复杂程序是否可以构造一种专门的针对性的程序来判定其是否可停机——如果可以，就是停机可判定，否则就是停机不可判定。
因而，对第一类停机判定图灵机的问题事实上就转化为：是否存在停机不可判定图灵机。
而对于第二类停机判定图灵机A，则可以将所有图灵机分为三类：可停机图灵机、不可停机图灵机，以及自指图灵机（显示1、2、3中的一个）。
对于这种分类，又能衍生出一些很有趣的问题。
比如，自指图灵机是否存在停机可判定的子集？
以及，自指图灵机是否可以同时也是可停机的？也就是虽然自指了，但程序依然可以停止——比如打印自身代码的图灵机，必然是自指的（当然，需要上位托管），但却是可停机的。
从而，对于自指图灵机，如何构造适配的特定停机判定呢？
另外，停机不可判定图灵机有哪些共性？是否存在不自指的停机不可判定图灵机？
暂时就想到这些。
其实核心想法很简单：扣除所有自指图灵机（或者说自指命题）以后，剩下的东西能干什么？如果一样能干很多事情的话，那是最好不过——如果不能的话，那都能干些什么呢？
2011-4-23 16:45:43反过来，你所说的那种针对特定程序B，判断它是否能停机的程序是否存在呢？答案只能是不一定，因为对于有些停机问题，即使人类也不知道它是否会停机（例如一个程序是验证哥德巴赫猜想，如果出现了反例就停机，否则就一直循环）。因为我们人类并不知道哥德巴赫猜想是否正确，所以我们也判断不出来这个程序是否停机。即使你已经等了10000年，程序一直没停，但是你还是不知道它在第10001年是否停机。那么，既然连人类都不知道这个程序是否停机，就更不可能创造出来一个程序来做此判断，问题的关键是，你虽然能够造出一个程序来判断运算哥德巴赫猜想的程序的某些特征（例如是否包含while(true)），但是你并不能保证仅仅根据这些有限的特征就能保证该判定程序是会输出正确答案的。所以，不存在你说的那种针对任意一个程序B，判定它是否停机的程序。
对于第二个问题，首先，我们判定一个程序中是否发生了自指本身就是一个不可判定问题，可以证明这类问题与图灵停机问题等价。实际上，对于一般的程序，不运行它，就来断言这个程序的某种运行之中的特性本身就是不可判定的。所以，判定一个程序是否发生自指本身就是不可判定的问题。LostAbaddon老弟终于从物理进入计算机世界了。
>LostAbaddon在讨论两个关于停机问题的问题中写道：
---------------------------
停机问题是一个很经典的问题，而且是一个很典型的不可解决问题。
这里不讨论停机问题。
从停机问题出发，我想到了另外两个问题，不知道这里有没有人之前想过。
因为觉......
2011-4-23 17:12:30第一段jake兄所给的，我看来应该不是我所要的。
第二段有问题。
Jake兄的结论应该是这个意思：针对任意程序B都制造A(B)来停机判定的可能应该是不能做到，但是对于部分B是可以做到的。
在这个情况下，请看我自己回复的那段。
第二个问题中，你所说的证明能否给一下（最好是严格的）？我对这个很有兴趣。
PS：我本就是IT人，不是物理人，不好意思。
[请在这里输入你的回复，不要在下面的空间内写，谢谢！劳驾您顺道把我也删了吧]
>jake在回复：讨论两个关于停机问题的问题中写道：
---------------------------
对于第一个问题，可以肯定的是，你可以写出一种对于一类自动机有效的判定停机问题的程序P，例如P就是检查输入的任意一个程序X是否包含while(true)这样的死循环。而且P可以作用到一切程序上......
2011-4-23 18:56:57Jake兄的结论应该是这个意思：针对任意程序B都制造A(B)来停机判定的可能应该是不能做到，但是对于部分B是可以做到的。
在这个情况下，请看我自己回复的那段。
你的问题是什么？我看你前一个回复没看懂，你能直接把问题说出来吗？
第二个问题，当然给出详细证明，在很多《计算理论》的书中都有指出。但是没有针对“自打印问题”的回答，我给出了我自己的一个简单证明：
其次，第二个可能隐藏观察者的地方就在于对“自我”的判断上。我们知道，蒯恩程序作用到自己的编码上就能够复制出一个自我出来。即Q(q)=”Q(q)”。对于计算机程序Q来说，它仅仅忠实地打印出了一个字符串“Q(q)”，这与打印出一个“Hello world”没有什么区别。我们之所以觉得这个Q(q)程序与众不同恰恰是因为作为一个观察者，我们能够发现“Q(q)”
与Q(q)的源代码是完全一样的。是观察程序运行的观察者判断出了这个Q(q)能够得到“自我”。这也与我们在第2章讨论的情形相一致，也就是说第一观察者“我”将观察箭头赋予了这个蒯恩程序Q(q)，所以“自我”是被观察而出的。
但是，也许你会反驳说：“不对，这种观察能力只不过是对字符串的比较。假如我写一个程序P，它也会分析该程序的源代码是否为程序的输出。这样不需要观察者，P就可以发现什么程序能够打印出‘自我’出来了。”
真的是这样吗？我们可以利用与图灵停机问题相同的技巧来说明这样的判断程序P不可能存在。我们不妨假设P存在，它能够判断出任意源代码为x的程序X作用到数据y上产生的输出X(y)是否与自己的源代码一致。
你大概已经猜到了我将会干什么，我可以构造一个程序D(z)为：
D(z){
If P(z,z)=0 then
Return Self;
Else
Return ‘ok’;
End if
}
源代码6：让判断是否可以打印自身源代码的程序P实效的程序
这个程序会来调用P这个程序，当P发现程序Z作用到数据z上面的时候得到了它自己的源代码（简写为Self），就返回一个字符串“ok”，否则将返回它自己的源代码加上数据z。P倒霉就倒霉在当把D这个程序自己的源代码d输入给D(z)它自己的时候，因为P无论怎样都一定会给出错误的判断！所以，我们只能反过头来说判断是否可以打印自身源代码的程序P不存在。
这样，一个程序是否能打印出和自己源程序一模一样的代码只能由计算机程序之外的观察者做出判断。所以，“自我”必然是被观察出来的。
原文见：http://www.swarmagents.cn/bs/download.php?id=308
>LostAbaddon在回复：讨论两个关于停机问题的问题中写道：
---------------------------
第一段jake兄所给的，我看来应该不是我所要的。
第二段有问题。
Jake兄的结论应该是这个意思：针对任意程序B都制造A(B)来停机判定的可能应该是不能做到，但是对于部分......
2011-4-23 23:00:05也就是，如果是说存在部分图灵机是可以建立停机判定图灵机的，而部分不行的话，那不能建立停机判定图灵机的那些图灵机的共性是什么？
举例来说，我们知道注入没有循环过程，也不调用外部程序与组件的程序是可以停机的（诸如DOS中调用批处理就算是调用外部程序了）。 那么，对于那些不能判定是否会停机的图灵机，其共性是什么你？
显然不是运行10000年都没结果……
进一步，我在考虑，这种图灵机与自指的图灵机的关系是什么样。从一种直观的角度来说，可以是while(1)这种无限循环，但也可能是因为自指。
于是，自指的图灵机与那些不能判定是否会停机的图灵机之间的关系是怎么样的呢？
至于第二部分，我似乎没说“自打印”啊……
我是想说，对于能否判断自指是否有证明。当然，自打印里自然也有自指了，但自指的图灵机未必都是自打印的图灵机。
而且，就这里构造的反例D(z)来看，显然可以判断出这个程序是建立了指向调用者自身的过程（你总是要把D输入到P中来构造悖论的吧？于是P(D)在判定看来是一个调用P的自指），因而返回状态1——出现自指。
比如说，要放在这个东西，建立这么一套：
P()是我所说的第二类停机判定图灵机，于是有：
D(z){
if(P(z,z)=1,2,3)return State1;
if(P(z,z)=4)return State2;
else return State3;
}
但，这种程序对于P是无效的，因为D中显含P，于是P(D)会返回2，因为D的内部变量指向了P而没有指向D自身，于是自然返回2。
这与Jake兄所给的自打印的判断是有本质上的区别的。
至少，在证明P不存在以前，说D是P的反例是毫无根据的。
[请在这里输入你的回复，不要在下面的空间内写，谢谢！劳驾您顺道把我也删了吧]
>jake在回复：讨论两个关于停机问题的问题中写道：
---------------------------
Jake兄的结论应该是这个意思：针对任意程序B都制造A(B)来停机判定的可能应该是不能做到，但是对于部分B是可以做到的。
......
2011-4-23 23:09:39上面一段有个地方写错了，不是出现P(D)，是出现了D(D)，而D有调用了P，所以最后用我的第二类判定图灵机得到的结果应该是3。
而且，就D和P的形式来看，似乎没有什么过程组织P对D的判定输出为3。
[请在这里输入你的回复，不要在下面的空间内写，谢谢！劳驾您顺道把我也删了吧]
>LostAbaddon在回复：讨论两个关于停机问题的问题中写道：
---------------------------
也就是，如果是说存在部分图灵机是可以建立停机判定图灵机的，而部分不行的话，那不能建立停机判定图灵机的那些图灵机的共性是什么？
举例来说，我们知道注入没有循环过程，也不调用外部程序与组......
2011-4-24 11:26:31也就是，如果是说存在部分图灵机是可以建立停机判定图灵机的，而部分不行的话，那不能建立停机判定图灵机的那些图灵机的共性是什么？
举例来说，我们知道注入没有循环过程，也不调用外部程序与组件的程序是可以停机的（诸如DOS中调用批处理就算是调用外部程序了）。 那么，对于那些不能判定是否会停机的图灵机，其共性是什么你？
显然不是运行10000年都没结果……
唯一的共性就是我们不能建立停机的判定程序。并不存在着一般的共性的判定条件。但是我们的确可以把这个集合的范围进行一定的缩小，例如对于不存在条件循环语句（就是do,while这类语句）的程序，他们肯定不是无法停机的程序。但是，在剩下的那些程序中，我们就不能判断了。就比如说这个while(true)之类的循环，虽然我们知道如果存在这条句子，它就不会停机，但是我们永远不可能知道，不包括这个句子的一般程序是否停机。
为什么说没用共性呢？就是因为一旦我们找到了这些程序的共性，而且这个共性是可描述清楚的，那么它必然也是可计算的（尚不存在定义清晰的不可计算过程），于是我们就找到了一个判定任意程序是否停机的程序了。
进一步，我在考虑，这种图灵机与自指的图灵机的关系是什么样。从一种直观的角度来说，可以是while(1)这种无限循环，但也可能是因为自指。
于是，自指的图灵机与那些不能判定是否会停机的图灵机之间的关系是怎么样的呢？
你始终存在着一种错误的认识：自指是一种可以被计算机程序发现的可计算的属性，但实际上这种属性是不可计算的。就像程序是否可以停机这样一个看起来很显然而简单的属性都是不可计算的一样，一个程序中是否存在着自指也是不可计算的。你当然可以说自指是不可判定是否停机的一种共性，但是我们针对这种共性说不了太多事情，就是因为它是不可计算的。虽然我们可以明确知道对于特定的程序是否为自指的（例如自打因程序），但是对于更一般的程序，我们就无法判断他是否具有自指特性了。
至于第二部分，我似乎没说“自打印”啊……
一样的，“自打印”是我们已知的自指程序的最小核心。所以，可以用它作为例子来说明。
我是想说，对于能否判断自指是否有证明。当然，自打印里自然也有自指了，但自指的图灵机未必都是自打印的图灵机。
是的，通过自打印技术（即蒯恩），你是可以构造任意一种具有自指属性但是还有更多复杂功能的程序的， 这就是http://www.swarmagents.cn/bs/download.php?id=308 一文所说的递归定理！但是反过来，给你一个一般的程序，你是无法判定它是否包含了自打印。
而且，就这里构造的反例D(z)来看，显然可以判断出这个程序是建立了指向调用者自身的过程（你总是要把D输入到P中来构造悖论的吧？于是P(D)在判定看来是一个调用P的自指），因而返回状态1——出现自指。
调用自身这件事情并不是看起来那么简单，当然，对于直接调用自身，你会很清楚地看出来，甚至可以写一个判定程序。但是，还有很多的间接调用自身的方法，你就不能用机械的步骤判断出来系统是否再调用自身了。比如说那个自打印程序就是一种间接调用自身的好例子。它在自己的源程序中没有任何一处包含着自己的源代码这样的东西，但是让你从整体上看来，它就是在调用自己的源代码。也就是说，理解蒯恩（自打印）程序最核心的地方在于，你需要从两个层次看系统，一个层次是把你自己当作计算机，你去机械的做一些步骤，在这个层次你看不出是在调用自己，但是，作为观察者，你还可以跳出细节，看待整体，这个时候你便可以发现系统是在调用自身。这一点是理解递归定理最最核心的地方，所以我强烈建议你看http://www.swarmagents.cn/bs/download.php?id=308 这篇长文，深刻理解递归定理、蒯恩等的含义。否则你很多观点实际上都是有误区的。
比如说，要放在这个东西，建立这么一套：
P()是我所说的第二类停机判定图灵机，于是有：
D(z){
if(P(z,z)=1,2,3)return State1;
if(P(z,z)=4)return State2;
else return State3;
}
但，这种程序对于P是无效的，因为D中显含P，于是P(D)会返回2，因为D的内部变量指向了P而没有指向D自身，于是自然返回2。
这与Jake兄所给的自打印的判断是有本质上的区别的。
至少，在证明P不存在以前，说D是P的反例是毫无根据的。
这段我完全没看懂，这里面的P是什么？z是什么？State1,2是什么？另外，其实还有一个重要的概念在讨论前你没有界定清楚。就是自指。究竟什么叫做自指？在你的讨论中，你没有定义它。但是在我的讨论中，这个自指是有明确定义的，这个定义就是说：如果一个程序P，它的源代码是c(P)，还有任意一个程序F，那么如果执行程序P的结果完全等效于执行F(c(P))的结果，我们就说程序P是自指的程序。说白了也就是，这个程序P看起来可以把自己的源代码掏出来执行任意的操作（即程序实现了调用自身）。关于这个东西还是要参考我那篇文章http://www.swarmagents.cn/bs/download.php?id=308中的“递归定理”那一段。否则我们的讨论就会建立在不一致的基本概念之上了。
总之，我所说的核心内容是：不存在判定程序是否自指的一般方法；我们知道一种构造自指程序的一般方法，就是利用自打印技术，也就是蒯恩程序。可构造但是不可判定，这听起来似乎有点反直觉，但是这的确是数理逻辑、递归函数论中的一个重要结论：递归可枚举集并不一定都是递归集。>LostAbaddon在回复：讨论两个关于停机问题的问题中写道：
---------------------------
也就是，如果是说存在部分图灵机是可以建立停机判定图灵机的，而部分不行的话，那不能建立停机判定图灵机的那些图灵机的共性是什么？
举例来说，我们知道注入没有循环过程，也不调用外部程序与组......
2011-4-24 12:07:19我这里自指的意义在主楼就说过了：
（我所说的）自指，就是在图灵机运行过程中出现某个变量（或者指针）指向该图灵机自身。
也可以具体说为：如果将所有变量（包括图灵机）都符号化，有各自的符号，那如果存在某个变量通过一系列指向链能指向图灵机自身，就是自指。
这个在主楼就说过了。
[请在这里输入你的回复，不要在下面的空间内写，谢谢！劳驾您顺道把我也删了吧]
>jake在回复：讨论两个关于停机问题的问题中写道：
---------------------------
也就是，如果是说存在部分图灵机是可以建立停机判定图灵机的，而部分不行的话，那不能建立停机判定图灵机的那些图灵机的共性是什么？
2011-4-24 16:13:23这就是我所说的直接自指，也是一种最平凡的自指，也可以把它叫做程序的自调用，比如说递归程序。但是，这种程序实际上不可能真正完成把自己完全一模一样的调用、包含进来。就像你写汉诺塔程序，你一定存在一个终止调用的语句，从而使递归结束。
但是，我所说的是一种间接自指，根本不需要调用自己的这种途径实现诸如打印自己源代码的操作。
包括在图灵停机问题中，D(d)中的这个d并不是指向一个函数的指针，而是对D这个程序的编码，也就是说d并不是D，这是重要的区别。>LostAbaddon在回复：讨论两个关于停机问题的问题中写道：
---------------------------
我这里自指的意义在主楼就说过了：
（我所说的）自指，就是在图灵机运行过程中出现某个变量（或者指针）指向该图灵机自身。
也可以具体说为：如果将所有变量（包括图灵机）都符号化......
2011-4-24 17:06:36汉诺塔的例子不是好例子。
因为我是想区分是能否指向自己、不能指向自己且能停机、不能指向自己且不能停机。
既然如此，汉诺塔的例子当然是指向了自己，是否能停机已经不重要了。
在后面的说法中，有一个问题是值得考虑的：
你要调用图灵机的代码，然后说因为不是直接调用图灵机自身，所以不是自指。但是上位托管机制如何知道你调用的是谁？总要有个判定吧，这不就要和该图灵机打交道了？
如果说，把所有上位托管机制都认为不存在，那其实就等于是说这里调用了代码，我也不知道代码怎么调用的，反正调用了，我也不知道调用的对不对，反正我相信对的。
这不合理吧？
以DOM对象为例，JS调用浏览器的DOM对象处理机制来调用DOM，而这个DOM含有JS自身，这里浏览器DOM处理机制就是上位托管者。
我也可以说：这里没有自指，我就是调用了文档代码嘛，哪有自指？
当然，上面文字中所有的“自指”都是直接自指。
如果因为间接自指不显式地明确告诉使用者我调用了自己而说这里不调用自己，这是一种黑盒操作，只不过把过程交给了一个未知罢了。
[请在这里输入你的回复，不要在下面的空间内写，谢谢！劳驾您顺道把我也删了吧]
>jake在回复：讨论两个关于停机问题的问题中写道：
---------------------------
这就是我所说的直接自指，也是一种最平凡的自指，也可以把它叫做程序的自调用，比如说递归程序。但是，这种程序实际上不可能真正完成把自己完全一模一样的调用、包含进来。就像你写汉诺塔程序，你一定存在......
