Misplaced Pages

Mortality (computability theory)

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
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 Π 2 0 {\displaystyle \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 R n {\displaystyle {\mathbb {R} }^{n}} or Q n {\displaystyle {\mathbb {Q} }^{n}} or Z n {\displaystyle {\mathbb {Z} }^{n}} , for n ≥ 2 {\displaystyle n\geq 2} , where the transition function is piecewise linear (here, an arbitrary point, e.g., the origin, is selected as a halting state).

References

  1. ^ Hooper, P. "The undecidability of the Turing machine immortality problem". Journal of Symbolic Logic. 31 (2): 219–234. doi:10.2307/2269811.
  2. Herman, Gabor. "A simple solution of the uniform halting problem". Journal of Symbolic Logic. 34 (4): 639–640. doi:10.2307/2270856.
  3. Kurtz, Stuart A.; Simon, Janos (2007). "The undecidability of the generalized Collatz problem". International Conference on Theory and Applications of Models of Computation, TAMC 2007. doi:10.1007/978-3-540-72504-6_49.
  4. Blondel, Vincent D.; Bournez, Olivier; Koiran, Pascal; Papadimitriou, Christos H.; Tsitsiklis, John N. (2001-03-28). "Deciding stability and mortality of piecewise affine dynamical systems" (PDF). Theoretical Computer Science. 255 (1): 687–696. doi:10.1016/S0304-3975(00)00399-6. ISSN 0304-3975.
  5. Ben-Amram, Amir M. (2015-01-01). "Mortality of iterated piecewise affine functions over the integers: Decidability and complexity". Computability. 4 (1): 19–56. doi:10.3233/COM-150032. ISSN 2211-3568.


Stub icon

This computer science article is a stub. You can help Misplaced Pages by expanding it.

Categories: