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