Geodesic
Some undecidable problems about the trace-subshift associated to a Turing machine
Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 2.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2015_17_2_a9,
     author = {Gajardo, Anah{\'\i} and Ollinger, Nicolas and Torres-Avil\'es, Rodrigo},
     title = {Some undecidable problems about the trace-subshift associated to a {Turing} machine},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {17},
     number = {2},
     year = {2015-2016},
     doi = {10.46298/dmtcs.2137},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2137/}
}
TY  - JOUR
AU  - Gajardo, Anahí
AU  - Ollinger, Nicolas
AU  - Torres-Avilés, Rodrigo
TI  - Some undecidable problems about the trace-subshift associated to a Turing machine
JO  - Discrete mathematics & theoretical computer science
PY  - 2015-2016
VL  - 17
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2137/
DO  - 10.46298/dmtcs.2137
LA  - en
ID  - DMTCS_2015_17_2_a9
ER  - 
%0 Journal Article
%A Gajardo, Anahí
%A Ollinger, Nicolas
%A Torres-Avilés, Rodrigo
%T Some undecidable problems about the trace-subshift associated to a Turing machine
%J Discrete mathematics & theoretical computer science
%D 2015-2016
%V 17
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2137/
%R 10.46298/dmtcs.2137
%G en
%F DMTCS_2015_17_2_a9
Gajardo, Anahí; Ollinger, Nicolas; Torres-Avilés, Rodrigo. Some undecidable problems about the trace-subshift associated to a Turing machine. Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 2. doi : 10.46298/dmtcs.2137. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2137/

Cité par Sources :