確定一個圖靈機對於給定的特定輸入程式是否會停止執行。停機問題對於少於四個狀態的機器是可解的。然而，四狀態情況是開放的，五狀態情況幾乎可以肯定無法解決，因為它包括迭代類似考拉茲同餘函式的機器，而這些特定問題目前是開放的。通用圖靈機是否停機的問題是不可判定的，正如圖靈首次證明的那樣 (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.tw/HaltingProblem.html