On Immortal Configurations in Turing Machines
Abstract
We investigate the immortality problem for Turing machines and prove that there exists a Turing Machine that is immortal but halts on every recursive configuration. The result is obtained by combining a new proof of Hooper's theorem [11] with recent results on effective symbolic dynamics.
Domains
Discrete Mathematics [cs.DM]| Origin | Files produced by the author(s) |
|---|
Loading...