Gajardo, Anahí and Ollinger, Nicolas and Torres-Avilés, Rodrigo - Some undecidable problems about the trace-subshift associated to a Turing machine

dmtcs:2137 - Discrete Mathematics & Theoretical Computer Science, December 2, 2015, Vol. 17 no.2
Some undecidable problems about the trace-subshift associated to a Turing machine

Authors: Gajardo, Anahí and Ollinger, Nicolas and Torres-Avilés, Rodrigo

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 by 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 are shown to be undecidable for the class of reversible Turing machines.


Source : oai:HAL:hal-01349052v1
Volume: Vol. 17 no.2
Section: Automata, Logic and Semantics
Published on: December 2, 2015
Submitted on: September 8, 2014
Keywords: Turing machine,discrete-time dynamical system,subshift,formal language,entropy,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 41 times.
This article's PDF has been downloaded 64 times.