Anahí Gajardo ; Nicolas Ollinger ; Rodrigo Torres-Avilés - 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 - https://doi.org/10.46298/dmtcs.2137
Some undecidable problems about the trace-subshift associated to a Turing machineArticle

Authors: Anahí Gajardo 1,2; Nicolas Ollinger ORCID3; Rodrigo Torres-Avilés 1,2

  • 1 Departamento de Ingeniería Matemática
  • 2 Centro de Investigación en Ingeniería Matemática [Concepción]
  • 3 Laboratoire d'Informatique Fondamentale d'Orléans


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.

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

2 Documents citing this article

Share and export

Consultation statistics

This page has been seen 769 times.
This article's PDF has been downloaded 651 times.