确定一个图灵机对于给定的特定输入程序是否会停止运行。停机问题对于少于四个状态的机器是可解的。然而，四状态情况是开放的，五状态情况几乎可以肯定无法解决，因为它包括迭代类似考拉兹同余函数的机器，而这些特定问题目前是开放的。通用图灵机是否停机的问题是不可判定的，正如图灵首次证明的那样 (Wolfram 2002, pp. 1136-1138)。
停机问题
另请参阅
忙碌的海狸, 蔡廷常数, 图灵机, 不可判定性使用 探索
参考文献
Chaitin, G. J. "Computing the Busy Beaver Function." §4.4 in Open Problems in Communication and Computation (Ed. T. M. Cover and B. Gopinath). New York: Springer-Verlag, pp. 108-112, 1987.Davis, M. "What Is a Computation." In Mathematics Today: Twelve Informal Essays (Ed. L. A. Steen). New York: Springer-Verlag, pp. 241-267, 1978.Penrose, R. The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics. Oxford, England: Oxford University Press, pp. 63-66, 1989.图灵, A. M. "On Computable Numbers, with an Application to the Entscheidungsproblem." Proc. London Math. Soc. Ser. 2 42, 230-265, 1937. Reprinted in The Undecidable (Ed. M. David). Hewlett, NY: Raven Press, 1965.图灵, A. M. "Correction to: On Computable Numbers, with an Application to the Entscheidungsproblem." Proc. London Math. Soc. Ser. 2 43, 544-546, 1938.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 1136-1138, 2002.请这样引用
Eric W. Weisstein "停机问题。" 来自 Web 资源。 https://mathworld.net.cn/HaltingProblem.html