停机问题学习笔记
Turing Machine
前段时间看到 Scott H Young 那篇介绍费曼技巧 [1] 的文章，一下想到了程序员界流传甚广的小黄鸭调试法（Rubber Duck Debugging） [2] 。几天前晚上散步的时候，聊天儿时提起了罗素悖论，让我联想到图灵对停机问题精妙的解法。想拿这个试试费曼技巧，讲到一半发现卡壳了，自己把自己绕了进去。我想到刘未鹏说过的那种状态，学习一个算法，初看觉得太牛逼了，然后花十分钟理解了人家花了十年才想出的成果，再花十天完全忘记，只能想起那个算法十分精妙，该不会的还是不会。所以应该由本溯源地学习数学和算法，并且写一个博客记录下学习的过程。于是这篇就作为费曼技巧和写作学习实践的第一篇。
在计算机科学领域，最广为人知的问题是关于 P 与 NP 问题的讨论，但不论 P 还是 NP，它们只是对解决问题效率的讨论。其实还有一类问题，它们难到计算机永远无法解出，这类问题被称作不可判定问题（Undecidable Problem） [3] ，其中一个可能是最有名的问题就是停机问题。
停机问题提出了这样的疑问：是否存在一个程序，可以判定任何一个程序是否会停止。
要解决这个问题，我们先假设存在一个程序满足上述条件，比如：
int yourBrilliantProgram(char * program, inputType input){
if (program(input) stops)
return 1;
else //It loops forever
return 0;
}
其中，第一个 if 语句中的判断是人类智慧的结晶，它用了神奇的方法得知了 program(input) 是否停止。
接着我们就要进行破坏了，再来考虑这样一个程序：
int myDisgustingProgram(char * program){
if (yourBrilliantProgram(program, program)){
while(1);
return 0; //Never reaches here
}
else
return 1;
}
我的程序专门跟你作对，如果你说这个程序可以正常退出，那么我就作一个死循环；你说它是死循环的，我就正常退出给你返回一个true。
So far so good.
最精彩的地方来了，考虑 yourBrilliantProgram(myDisgustingProgram, myDisgustingProgram) 的返回值。这里有点绕，我们一步一步跟踪。
首先，进入 yourBrilliantProgram 的第一个判断语句，这里执行 myDisgustingProgram(myDisgustingProgram) ，进入 if(yourBrilliantProgram(myDisgustingProgram, myDisgustingProgram)) 这一句。这里可能出现两个结果：
- 返回
1，说明myDisgustingProgram(myDisgustingProgram)正常退出，那么当前程序进入死循环，此时上一层的yourBrilliantProgram()应该检测到这个死循环，并返回0，说明myDisgustingProgram(myDisgustingProgram)是个死循环。矛盾。 - 返回
0，说明myDisgustingProgram(myDisgustingProgram)死循环，那么当前程序返回1并且正常退出，又证明myDisgustingProgram(myDisgustingProgram)不是死循环。矛盾。
也就证明，根本不存在这样的程序可以判定任何一个程序是否停止。
