Mortality (computability theory)

In <a href="/facts/Computability_theory/cqDfXwdf">computability theory</a>, the mortality problem is a <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a> related to the <a href="/facts/Halting_problem/Xz1bac40">halting problem</a>. For <a href="/facts/Turing_machine/ojCtglYu">Turing machines</a>, the halting problem can be stated as follows:
Given a <a href="/facts/Turing_machine/ojCtglYu">Turing machine</a>, and an input, decide whether the machine halts when run on the given input.
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 <a href="/facts/Undecidable_problem/QBxmXBbY">undecidable</a>. 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 <a href="/facts/Arithmetical_hierarchy/rQptcBFK">
 
 
 
 
 Π
 
 2
 
 
 0
 
 
 
 
 {\displaystyle \Pi _{2}^{0}}
 
-complete</a>.

Mortality (computability theory) open-in-new

Mortality (computability theory)