The halting problem asks, given a program and an input, whether running that program on that input eventually stops. It is undecidable: no total algorithm answers correctly for every encoded program and input.
If a decider existed, construct a program that loops when predicts halting and stops when it predicts nonhalting. Running on its own description contradicts either prediction. Halting instances are nevertheless computably enumerable, since finite simulations eventually witness any halt. If nonhalting instances were also computably enumerable, dovetailing the two recognizers would decide the problem, so their complement is not enumerable.
A machine's halting times admit a total computable function as a bound on all inputs in its domain if and only if that domain is a computable set. A bound decides the domain by finite simulation; conversely, a domain decider allows returning zero outside the domain and the exactly simulated halting time inside it. In particular every machine computing a total computable function has an exact computable running-time function, while nontotal machines may or may not have total bounds.
The halting set of a Turing machine is the set of inputs on which it eventually halts. For a deterministic machine with a designated terminal state, eventual halting is invariant along every transition edge, even when that edge is traversed backwards. This observation justifies passing from forward computations to symmetric equality derivations in a semigroup presentation.
For an effective enumeration of unary partial computable functions, the diagonal halting set is
Equivalently, for an enumeration of computably enumerable sets, .
Every recursively enumerable set many-one reduces to the diagonal halting set. If a program halts exactly on , the S-m-n theorem produces from an index for a unary program that ignores its input and performs that computation on . Then
Conversely, a computable preimage of a recursively enumerable set is recursively enumerable.
If , then
differs from , while the computable map proves .
The set is also a computably enumerable set, so the many-one completeness of the halting problem gives . Together the two many-one reductions place and in the same many-one degree.

Ancestors (6)

  1. Recursively enumerable language
  2. Formal language theory
  3. Foundations of mathematics
  4. Area of mathematics
  5. Mathematics
  6. Home

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (2)

The Halting problem is a fundamental concept in computability theory, introduced by British mathematician and logician Alan Turing in 1936. It is a decision problem that can be stated as follows: Given a description of a program (or Turing machine) and an input, determine whether the program finishes running (halts) or continues to run indefinitely. Turing proved that there is no general algorithm that can solve the Halting problem for all possible program-input pairs.