Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T18:07:20.242Z Has data issue: false hasContentIssue false

The undecidability of the Turing machine immortality problem1

Published online by Cambridge University Press:  12 March 2014

Philip K. Hooper*
Affiliation:
Harvard University

Extract

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.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1966

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

Article purchase

Temporarily unavailable