A small minimal aperiodic reversible Turing machine

作者：

Highlights：

• We present a complete and reversible Turing machine which is aperiodic.

• We prove that its associated dynamical system is time symmetric and minimal.

• The column shift of the presented machine is proved to be substitutive.

• We prove the undecidability of the existence of a periodic orbit in Turing machines.

摘要

•We present a complete and reversible Turing machine which is aperiodic.•We prove that its associated dynamical system is time symmetric and minimal.•The column shift of the presented machine is proved to be substitutive.•We prove the undecidability of the existence of a periodic orbit in Turing machines.

论文关键词：Turing machines,Discrete dynamical systems,Symbolic dynamics

论文评审过程：Received 11 May 2014, Revised 28 September 2016, Accepted 3 October 2016, Available online 19 October 2016, Version of Record 14 November 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.10.004