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 3; 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
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]

2 Documents citing this article

Share and export

Consultation statistics

This page has been seen 564 times.
This article's PDF has been downloaded 474 times.