确定一个图灵机对于给定的特定输入程序是否会停止运行。停机问题对于少于四个状态的机器是可解的。然而，四状态情况是开放的，五状态情况几乎可以肯定无法解决，因为它包括迭代类似考拉兹同余函数的机器，而这些特定问题目前是开放的。通用图灵机是否停机的问题是不可判定的，正如图灵首次证明的那样 (Wolfram 2002, pp. 1136-1138)。
停机问题
另请参阅
忙碌的海狸, 蔡廷常数, 图灵机, 不可判定性使用 Wolfram|Alpha 探索
参考文献
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 "停机问题。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/HaltingProblem.html