Skip to main content
MathOverflow

Return to Answer

replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 3

[I know this has already been answered satisfactorily, but for the sake of future readers, here's some additional terminology and an additional reference.]

These are also known as mortal Turing machines. See, e.g., this answerthis answer. Also discussed in

Hooper, P. K. The Undecidability of the Turing Machine Immortality Problem. J. Symb. Logic, 1966.

The key to the proof in the above paper is avoiding infinite loops starting from unreachable (finite) configurations, which is the same as the key to the construction alluded to in the question.

(This paper also contains the great line: "Most of the detailed work has been banished to the Appendices, to give the casual reader an opportunity to sample the flavor of the construction without choking on its bones.")

Note, however, that some authors use the term "mortal" differently, e.g. Hughes in "Undecidability of finite convergence for concatenation, insertion and bounded shuffle operators" uses it to mean a TM that halts on all configurations including infinite ones, and he proves that any such TM runs in $O(1)$ time, so this version of mortality is obviously too strong for most purposes.

[I know this has already been answered satisfactorily, but for the sake of future readers, here's some additional terminology and an additional reference.]

These are also known as mortal Turing machines. See, e.g., this answer. Also discussed in

Hooper, P. K. The Undecidability of the Turing Machine Immortality Problem. J. Symb. Logic, 1966.

The key to the proof in the above paper is avoiding infinite loops starting from unreachable (finite) configurations, which is the same as the key to the construction alluded to in the question.

(This paper also contains the great line: "Most of the detailed work has been banished to the Appendices, to give the casual reader an opportunity to sample the flavor of the construction without choking on its bones.")

Note, however, that some authors use the term "mortal" differently, e.g. Hughes in "Undecidability of finite convergence for concatenation, insertion and bounded shuffle operators" uses it to mean a TM that halts on all configurations including infinite ones, and he proves that any such TM runs in $O(1)$ time, so this version of mortality is obviously too strong for most purposes.

[I know this has already been answered satisfactorily, but for the sake of future readers, here's some additional terminology and an additional reference.]

These are also known as mortal Turing machines. See, e.g., this answer. Also discussed in

Hooper, P. K. The Undecidability of the Turing Machine Immortality Problem. J. Symb. Logic, 1966.

The key to the proof in the above paper is avoiding infinite loops starting from unreachable (finite) configurations, which is the same as the key to the construction alluded to in the question.

(This paper also contains the great line: "Most of the detailed work has been banished to the Appendices, to give the casual reader an opportunity to sample the flavor of the construction without choking on its bones.")

Note, however, that some authors use the term "mortal" differently, e.g. Hughes in "Undecidability of finite convergence for concatenation, insertion and bounded shuffle operators" uses it to mean a TM that halts on all configurations including infinite ones, and he proves that any such TM runs in $O(1)$ time, so this version of mortality is obviously too strong for most purposes.

Source Link
Joshua Grochow
Joshua Grochow
  • 3.2k
  • 1
  • 25
  • 37

[I know this has already been answered satisfactorily, but for the sake of future readers, here's some additional terminology and an additional reference.]

These are also known as mortal Turing machines. See, e.g., this answer. Also discussed in

Hooper, P. K. The Undecidability of the Turing Machine Immortality Problem. J. Symb. Logic, 1966.

The key to the proof in the above paper is avoiding infinite loops starting from unreachable (finite) configurations, which is the same as the key to the construction alluded to in the question.

(This paper also contains the great line: "Most of the detailed work has been banished to the Appendices, to give the casual reader an opportunity to sample the flavor of the construction without choking on its bones.")

Note, however, that some authors use the term "mortal" differently, e.g. Hughes in "Undecidability of finite convergence for concatenation, insertion and bounded shuffle operators" uses it to mean a TM that halts on all configurations including infinite ones, and he proves that any such TM runs in $O(1)$ time, so this version of mortality is obviously too strong for most purposes.