Mortality (computability theory)
Encyclopedia
In computability theory
, the mortality problem is a decision problem
which can be stated as follows:
In the statement above, the configuration is a pair, where q is one of the machine's states (not necessarily its initial state) and w is an infinite sequence of symbols representing the initial content of the tape. Note that 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
. However, it can be shown that the set of Turing machines which are mortal (i.e. halt on every starting configuration) is recursively enumerable.
Computability theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, the mortality problem is a decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
which can be stated as follows:
- Given a Turing machineTuring machineA Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
, decide whether it halts when run on any configuration (not necessarily a starting one)
In the statement above, the configuration is a pair
Philip K. Hooper proved in 1966 that the mortality problem is undecidable
Undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....
. However, it can be shown that the set of Turing machines which are mortal (i.e. halt on every starting configuration) is recursively enumerable.