Mortality (computability theory)

Last updated June 16, 2024

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^[1] 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,^[2] 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.^[1]
Counter machines ^[3]
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^[4]^[5] (here, an arbitrary point, e.g., the origin, is selected as a halting state).

Related Research Articles

In the computer science subfield of algorithmic information theory, a Chaitin constant or halting probability is a real number that, informally speaking, represents the probability that a randomly constructed program will halt. These numbers are formed from a construction due to Gregory Chaitin.

In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior, unlike a syntactic property. A non-trivial property is one which is neither true for every program, nor false for every program.

A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algorithm.

The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.

In theoretical computer science, the busy beaver game aims at finding a terminating program of a given size that produces the most output possible. Since an endlessly looping program producing infinite output or running for infinite time is easily conceived, such programs are excluded from the game. This is sometimes also formulated as finding the machine that runs for the longest time, but both games are similarly difficult.

In computer science, a universal Turing machine (UTM) is a Turing machine capable of computing any computable sequence, as described by Alan Turing in his seminal paper "On Computable Numbers, with an Application to the Entscheidungsproblem". Common sense might say that a universal machine is impossible, but Turing proves that it is possible. He suggested that we may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions ; which will be called " $m$ -configurations". He then described the operation of such machine, as described below, and argued:

It is my contention that these operations include all those which are used in the computation of a number.

Hypercomputation or super-Turing computation is a set of hypothetical models of computation that can provide outputs that are not Turing-computable. For example, a machine that could solve the halting problem would be a hypercomputer; so too would one that could correctly evaluate every statement in Peano arithmetic.

In the theory of computation, a tag system is a deterministic model of computation published by Emil Leon Post in 1943 as a simple form of a Post canonical system. A tag system may also be viewed as an abstract machine, called a Post tag machine —briefly, a finite-state machine whose only tape is a FIFO queue of unbounded length, such that in each transition the machine reads the symbol at the head of the queue, deletes a constant number of symbols from the head, and appends to the tail a symbol-string that depends solely on the first symbol read in this transition.

Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem.

Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines. Any definition, however, must make reference to some specific model of computation but all valid definitions yield the same class of functions. Particular models of computability that give rise to the set of computable functions are the Turing-computable functions and the general recursive functions.

In computability theory, a Turing reduction from a decision problem $to a decision problem is an oracle machine that decides problem given an oracle for . It can be understood as an algorithm that could be used to solve if it had available to it a subroutine for solving . The concept can be analogously applied to function problems.$

In computability theory, a decider is a Turing machine that halts for every input. A decider is also called a total Turing machine as it represents a total function.

In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi-Thue system, is a rewriting system over strings from a alphabet. Given a binary relation $between fixed strings over the alphabet, called rewrite rules, denoted by, an SRS extends the rewriting relation to all strings in which the left- and right-hand side of the rules appear as substrings, that is, where,,, and are strings.$

In logic, finite model theory, and computability theory, Trakhtenbrot's theorem states that the problem of validity in first-order logic on the class of all finite models is undecidable. In fact, the class of valid sentences over finite models is not recursively enumerable.

In computer science, a computation history is a sequence of steps taken by an abstract machine in the process of computing its result. Computation histories are frequently used in proofs about the capabilities of certain machines, and particularly about the undecidability of various formal languages.

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether an arbitrary program eventually halts when run.

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. The halting problem is undecidable, meaning that no general algorithm exists that solves the halting problem for all possible program–input pairs. The problem comes up often in discussions of computability since it demonstrates that some functions are mathematically definable but not computable.

Generic-case complexity is a subfield of computational complexity theory that studies the complexity of computational problems on "most inputs".

In computer science, a channel system is a finite state machine similar to communicating finite-state machine in which there is a single system communicating with itself instead of many systems communicating with each other. A channel system is similar to a pushdown automaton where a queue is used instead of a stack. Those queues are called channels. Intuitively, each channel represents a sequence a message to be sent, and to be read in the order in which they are sent.

References

1 2 Hooper, P. "The undecidability of the Turing machine immortality problem". Journal of Symbolic Logic. 31 (2): 219–234. doi:10.2307/2269811.
↑ Herman, Gabor. "A simple solution of the uniform halting problem". Journal of Symbolic Logic. 34 (4): 639–640. doi:10.2307/2270856.
↑ 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.
↑ 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.
↑ 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.

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:0-1] 1 2 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.

[1]

[2]

[3]

[4]

[5]