Preprint 2015-15
Anahi Gajardo, Nicolas Ollinger, Rodrigo Torres:
Some undecidable problems about the trace-subshift associated to a Turing machine
Abstract:
We consider three problems related to dynamics of one-tape Turing machines: Existence of blocking configurations, surjectivity in the trace, and entropy positiveness. In order to address them, a reversible two-counter machine is simulated in a reversible Turing machine on the right side of its tape. By completing the machine in different ways, we prove that none of the former problems is decidable. In particular, the problems about blocking configurations and entropy result undecidable for the class of reversible machines.
This preprint gave rise to the following definitive publication(s):
Anahi GAJARDO, Nicolas OLLINGER, Rodrigo TORRES: Some undecidable problems about the trace-subshift associated to a Turing machine. Discrete Mathematics & Theoretical Computer Science, vol. 17, 2, pp. 267-284, (2015).