Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

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 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Tuesday, July 26, 2016 - 5:24:03 PM
Last modification on : Tuesday, October 12, 2021 - 5:20:39 PM


Explicit agreement for this submission



Anahí Gajardo, Nicolas Ollinger, Rodrigo Torres-Avilés. Some undecidable problems about the trace-subshift associated to a Turing machine. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.267-284. ⟨10.46298/dmtcs.2137⟩. ⟨hal-01349052⟩



Record views


Files downloads