停机问题的证明

停机问题的证明

证明一个图灵机是否会停机：图灵会停机，即对任意的输入，我们都能判断其是否停机。我们都知道图灵机都能通过encode过程得到一个code，假设有这么一台图灵机Mm,m是其编号，只需证明无法判断Mm在m上是否停机不可解即可得证。假设我们有一个图灵机C，它的作用是copy自身，即对输入m，得到（m,m）。又构造另一个图灵机D，对于D，如果带子上1的个数大于1就停机，否则不停机。构造一个函数h，h（x,y）=1 如果图灵机Mx在y上停机，否则h(x,y)=2。第一步我们将C和h联合起来得到图灵机G(G的作用可以看成对于输入m，得到h（m,m），即Mm在m上停机时输出1，否则输出2)；第二步将G和D联合起来得到M，编号为m。根据上面的构造可知，Mm在m上停机，当且仅当Mm在m上不停机，矛盾，所以得证！