A small minimal aperiodic reversible Turing machine

Citation data:

Journal of Computer and System Sciences, ISSN: 0022-0000, Vol: 84, Page: 288-301

Publication Year:
2017
Usage 175
Abstract Views 163
Link-outs 12
Captures 1
Readers 1
Social Media 24
Shares, Likes & Comments 24
Citations 1
Citation Indexes 1
DOI:
10.1016/j.jcss.2016.10.004
Author(s):
Julien Cassaigne, Nicolas Ollinger, Rodrigo Torres-Avilés
Publisher(s):
Elsevier BV
Tags:
Mathematics, Computer Science
article description
A simple reversible Turing machine with four states, three symbols and no halting configuration is constructed that has no periodic orbit, simplifying a construction by Blondel, Cassaigne and Nichitiu and positively answering a conjecture by Kari and Ollinger. The constructed machine has other interesting properties: it is symmetric both for space and time and has a topologically minimal associated dynamical system whose column shift is associated to a substitution. Using a particular embedding technique of an arbitrary reversible Turing machine into the one presented, it is proven that the problem of determining if a given reversible Turing machine without halting state has a periodic orbit is undecidable.

This article has 0 Wikipedia mention.