The Halting Problem and the Mortality Problem in Computability Theory

The halting problem is one of the problems in the theory of algorithms , which can be stated informally as follows:

Given a description of a procedure and its initial input data, determine whether the execution of the procedure with this data will ever finish, or whether the procedure will keep running forever without stopping.

Alan Turing proved in 1936 that the halting problem is undecidable on a Turing machine. In other words, there is no general algorithm for solving this problem.

The halting problem occupies a central place in computability theory, since it is the first example of a problem that cannot be solved algorithmically.

In terms of functions, the problem can be described in accessible form as follows:

For any function F(G, start_state) that can determine whether another function halts, one can always write a function G(start_state) such that, when it is passed to F, the result of execution is the opposite of what F predicts.

For many other problems their algorithmic undecidability can be proved by trying to reduce them to the halting problem. This is done by contradiction: suppose there is some problem whose undecidability we need to establish. Assume that it is decidable, and try, using this fact, to write an algorithm that solves the halting problem. If this succeeds, we arrive at a contradiction, since it is known that no algorithm for the halting problem exists. Therefore the assumption was wrong, and the original problem is also undecidable.

Proof

Consider the set of algorithms that take a natural number as input and also produce a natural number as output. Choose some Turing-complete programming language. Each algorithm can be written as a finite sequence of symbols in this language. Order the set alphabetically. Each algorithm then gets its own ordinal number; moreover, there is an algorithm that, given the number of an element of , recovers its code in the chosen programming language. Let us call the Analyzer a hypothetical algorithm that receives as input a pair of natural numbers , and:

• halts and returns 1 if the algorithm with number does not halt when given input
• does not halt otherwise (if the algorithm with number halts when given input ).

The halting problem can be reformulated as follows: does the Analyzer exist?

Theorem. The Analyzer does not exist.

We prove this by contradiction. Suppose the Analyzer exists. Let us write an algorithm, the Diagonalizer, which takes a number as input, passes the pair of arguments to the Analyzer and returns the result of its work. In other words, the Diagonalizer halts if and only if the algorithm with number does not halt when given the number as input. Let be the ordinal number of the Diagonalizer in the set . Run the Diagonalizer, passing it this number . The Diagonalizer will halt if and only if the algorithm with number (that is, itself) does not halt when given the number as input (which is exactly what we passed to it). This contradiction shows that our assumption is false: the Analyzer does not exist, which is what was to be proved.

The mortality problem

In computability theory, the mortality problem is a decision problem related to the halting problem. For Turing machines, the halting problem can be stated as follows: given a Turing machine and a word, decide whether the machine halts when run on the given word.

In contrast, the mortality problem for Turing machines asks whether all runs of the machine, starting from any configuration, halt.

In the statement above, a configuration specifies the state of the machine (not necessarily its initial state), the position of its tape head, and the contents of its tape. Although we usually assume that in the initial configuration all but finitely many cells of the tape are blank, in the mortality problem the tape may have arbitrary contents, including infinitely many non-blank symbols written on it.

Philip K. Hooper proved in 1966 that the mortality problem is undecidable. This holds both for a machine with a tape that is infinite in both directions and for a machine with a semi-infinite tape. Note that this result does not follow directly from the well-known total function problem (does a given machine halt on every input?), since the latter problem concerns only valid computations (those starting from the initial configuration).

The variant in which only finite configurations are considered is also undecidable, as proved by Herman , who calls it the "uniform halting problem". He shows that the problem is not merely undecidable but -complete .

To avoid ambiguity, note that "matrix mortality" is a different problem, which is also undecidable.

Additional models

Naturally, the problem can be rephrased for any computational model that has notions of "configuration" and "transition". A member of the model is mortal if there is no configuration leading to an infinite chain of transitions. The mortality problem has turned out to be undecidable for:

• Semi-Thue systems and Markov algorithms.
• Dynamical systems over or or , for , where the transition function is piecewise linear (here an arbitrary point, for example the origin, is chosen as the halting state).

See also

• A control-flow graph can be used for quick categorization of whether a program has no loops (and therefore halts), has trivial loops (and therefore halts), has nontrivial loops (undecidable), or enters an infinite loop.