Mortality (computability theory)

Mortality (computability theory)

In computability theory, the mortality problem is a decision problem which can be stated as follows:

Given a Turing machine, decide whether it halts when run on any configuration (not necessarily a starting one)

In the statement above, the configuration is a pair <q, w>, 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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Mortality — is the condition of being mortal, or susceptible to death; the opposite of immortality. It may also refer to: Mortality rate, a measure of the number of deaths in a given population Case mortality rate, a measure of the number of deaths among a… …   Wikipedia

  • 20th century — For other uses, see 20th century (disambiguation). Millennium: 2nd millennium Centuries: 19th century · 20th century · 21st century Decades: 1900s 1910s …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”