The undecidability of the Turing machine immortality problem
- 1 June 1966
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 31 (2) , 219-234
- https://doi.org/10.2307/2269811
Abstract
A Turing Machine (TM) is an abstract, synchronous, deterministic computer with a finite number of internal states. It operates on the set of infinite words, or tapes, over some finite alphabet, scanning exactly one symbol of the tape at a time. (Only a 2-symbol alphabet, consisting of “0” and “|”, will be considered here, and the scanned symbol of a tape will be distinguished by an underscore.) depending upon its internal state and the symbol under scan, it can perform one or more of the following operations: replace the scanned symbol with a new symbol, focus its attention on an adjacent square, and transfer control to a new state.Keywords
This publication has 6 references indexed in Scilit:
- On formalisms for turing machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1964
- Computability of Recursive FunctionsJournal of the ACM, 1963
- Tag systems and lag systemsMathematische Annalen, 1963
- Turing-machines and the EntscheidungsproblemMathematische Annalen, 1962
- Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing MachinesAnnals of Mathematics, 1961
- A Variant to Turing's Theory of Computing MachinesJournal of the ACM, 1957