停机问题

停机问题是目前逻辑学的焦点，和第三而发次数学危机的解决方案。其本质问题是: 给定一个图灵机 T，和一坚啊个任意语言集合 S, 是否 T 会最终停机于每一个来自s∈S。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可列的(countable) S 也是360百科可停机的。

• 中文名 停机问题
• 外文名 halting problem
• 所属 逻辑学
• 实质 第三次数学危机的解决方案

概念

　　考通俗的说，停机问题课斤把跟全灯供肥就是判断任意一个程序是已名否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决，则有一个程序判断其本身是否会停机并做出相反的行为，这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。

　　停机问题本质是一高阶逻辑的不自恰性和不完备性。类似的命题有理发师悖论、全能悖论等。

证明

　　证明一个图灵机是否会停机:图灵会停机，即对任意的输入，我们都能判断其是否停机。我们都知道图灵机都能通过encode过药热程得到一个code，假设有这么一台图灵机Mm,m是其编来自号，只需证明无法刚毫判断Mm在m上是否停机不可解即可得证。假设我们有一个图灵机C，它的作用是copy自身，即对输入m，得到(m,m)。又构造360百科另一个图灵机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上不停机，矛盾，所以得证!