停机问题

停机问题是目前逻辑学的焦点，和第三次数学危机的解决方案。其本质问题是: 给定一个图灵机 T，和一个任意语言集合 S, 是否 T 会最终停机于每一个s∈S。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可列的(countable) S 也是可停机的。概念通俗的说，停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决，则有一个程序判断其本身是否会停机并做出相反的行为，这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。停机问题本质是一高阶逻辑的不自恰性和不完备性。类似的命题有理发师悖论、全能悖论等。证明证明一个图灵机是否会停机:图灵会停机，即对任意的输入，我们都能判断其是否停机。我们都知道图灵机都能通过encode过程得到一个code，假设有这么一台图灵机Mm,m是其编号，只需证明无法判断Mm在m上是否停机不可解即可得证。假设我们有一个图灵机C，它的作用是copy自身，即对输入m，得到(m,m)。又构造另一个图灵机D，对于D，如果带子上1的个数大于1就停机，否则不停机。构