Mortality (computability theory)

Not to be confused with Matrix 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 executions of the machine, starting from any configuration, halt.

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

Philip K. Hooper proved in 1966 that the mortality problem is undecidable. This is true both for a machine with a tape infinite in both directions, and for a machine with semi-infinite tape. Note that this result does not directly follow from the well-known total function problem (Does a given machine halt for every input?), since the latter problem concerns only valid computations (starting with an 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 just undecidable, but $\Pi _{2}^{0}$-complete.

Additional Models

The problem can naturally be rephrased for any computational model in which there are notions of "configuration" and "transition". A member of the model will be mortal if there is no configuration that leads to an infinite chain of transitions. The mortality problem has been proved undecidable for:

• Semi-Thue systems and Markov algorithms.
• Counter machines
• Dynamical systems over ${\mathbb {R} }^{n}$ or ${\mathbb {Q} }^{n}$ or ${\mathbb {Z} }^{n}$, for $n\geq 2$, where the transition function is piecewise linear (here, an arbitrary point, e.g., the origin, is selected as a halting state).