The unsolvability of the uniform halting problem for two state Turing machines

Journal of Symbolic Logic 34 (2):161-165 (1969)
  Copy   BIBTEX

Abstract

The uniform halting problem (UH) can be stated as follows:Give a decision procedure which for any given Turing machine (TM) will decide whether or not it has an immortal instantaneous description (ID).An ID is called immortal if it has no terminal successor. As it is generally the case in the literature (see e.g. Minsky [4, p. 118]) we assume that in an ID the tape must be blank except for some finite number of squares. If we remove this restriction the UH becomes the immortality problem (IP).

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,221

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Analytics

Added to PP
2009-01-28

Downloads
30 (#456,882)

6 months
1 (#1,027,696)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Computable Diagonalizations and Turing’s Cardinality Paradox.Dale Jacquette - 2014 - Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 45 (2):239-262.
Strong Computability and Variants of the Uniform Halting Problem.Gabor T. Herman - 1971 - Mathematical Logic Quarterly 17 (1):115-131.

Add more citations

References found in this work

Automata Studies.John Mccarthy & Claude Shannon - 1958 - Journal of Symbolic Logic 23 (1):59-60.

Add more references