Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-12T22:29:26.134Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  12 March 2014

Gabor T. Herman
Gabor T. Herman*
Affiliation:
IBM (United Kingdom), London
Get access Rights & Permissions [Opens in a new window]

Extract

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).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 34 , Issue 2 , 25 July 1969 , pp. 161 - 165
Copyright
Copyright © Association for Symbolic Logic 1969

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Fischer, P. C., On formalisms for Turing machines, Journal of the Association for Computing Machinery, vol. 12 (1965), pp. 570–580.Google Scholar
[2] Herman, G. T., The uniform halting problem for generalised one state Turing machines, Proceedings of the Ninth Annual Switching and Automata Theory Symposium, 1968.Google Scholar
[3] Hooper, P. K., The undecidability of the Turing machine immortality problem, this Journal , vol. 31 (1966), pp. 219–234.Google Scholar
[4] Minsky, M. L., Computation; finite and infinite machine, Prentice Hall, Englewood Cliffs, N.J., 1967.Google Scholar
[5] Shannon, C. E., A universal Turing machine with two internal states, Automata studies, Princeton, 1956, pp. 157–165.Google Scholar