停机问题 停机问题英語halting problem是逻辑数学中可计算性理论的一个问题通俗地说停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题该问题等价于如下的判定问题是否存在一个程序P对于任意输入的程序w能够判断w会在有限时间内结束或者死循环 艾伦图灵在年用對角論證法证明了不存在解决停机问题的通用算法这个证明的关键在于对计算机和程序的数学定义这被称为图灵机停机问题在图灵机上是不可判定问题这是最早提出的决定性问题之一 用数学语言描述则其本质问题为 给定一个图灵机T和一个任意语言集合S是否T会最终停机于每一个 s  S displaystyle sin S 其意义相同于可确定语言显然任意有限 S 是可判定性的可数的countableS 也是可停机的 停机问题包含了自我指涉本质是一阶逻辑的不完备性类似的命题有理发师悖论全能悖论等