The halting problem is the problem of determining whether a given program eventually halts on a given input. For Turing machines,
it is recursively undecidable. No algorithm
correctly answers this question for every program and
input (Turing 1937; Wolfram 2002, pp. 1136-1138).
The absence of a general algorithm does not prevent resolving particular finite collections of programs.
For example, Calude et al. (2002, pp. 366-367) determined which compressed
programs halt for a particular register
machine with total program and data length at most
84 bits. The counts at lengths bits, starting at , are 1, 1, 3, 8, 50, 311, ... (OEIS A400878;
Calude et al. 2002, p. 367). The machine's encoding
and treatment of run-time errors are part of the specification. The corresponding
weighted sum gives its halting
probability, a Chaitin's constant.
Calude, C. S.; Dinneen, M. J.; and Shu, C.-K. "Computing a Glimpse of Randomness." Exper. Math.11, 361-370,
2002. https://doi.org/10.1080/10586458.2002.10504481.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.Sloane,
N. J. A. Sequence A400878 in "The
On-Line Encyclopedia of Integer Sequences."Turing, A. M. "On
Computable Numbers, with an Application to the Entscheidungsproblem." Proc.
London Math. Soc. Ser. 242, 230-265, 1937. Reprinted in The Undecidable:
Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions
(Ed. M. Davis). Hewlett, NY: Raven Press, pp. 116-151, 1965.Turing,
A. M. "Correction to: On Computable Numbers, with an Application to the
Entscheidungsproblem." Proc. London Math. Soc. Ser. 243, 544-546,
1938.Veritasium. "The Simplest Math Problem No One Can Solve-Collatz
Conjecture." Jul. 30, 2021. https://www.youtube.com/watch?v=094y1Z2wpJg.Wolfram,
S. A
New Kind of Science. Champaign, IL: Wolfram Media, pp. 1136-1138, 2002.
bits, starting at 
, are 1, 1, 3, 8, 50, 311, ... (OEIS A400878;
Calude et al. 2002, p. 367). The machine's encoding
and treatment of run-time errors are part of the specification. The corresponding
weighted sum gives its halting
probability, a Chaitin's constant.
