arXiv:2611.00153 · v2
On Small Universal Reversible Turing Machines
摘要
A reversible Turing machine (RTM) is a Turing machine in which every instantaneous description has at most one predecessor. Writing for a universal RTM with states and symbols, we construct , , , , , , , , and ; each of them has fewer states or fewer symbols than each of the nine URTMs in Morita's book (2017). Most of them come from improved versions of Morita's conversions to three states, to four states, and to two symbols; for example, the improved conversion to three states uses symbols instead of . comes from merging two states of Morita's , recording the difference in tags on the tape cells, and then merging symbols, three times; one more such step gives . We also show that the halting problem of RTMs with at most two states is decidable for finite instantaneous descriptions, so that no RTM with at most two states is universal under any notion of universality that reduces the halting problem of Turing machines to it by a computable encoding into finite instantaneous descriptions; in particular, there is no URTM with at most two states in our formalization of Morita's definition. We also show that no three-state, two-symbol RTM is universal in that formalization.
作者备注:The constructions and the nonexistence results are formalized in Lean 4 with Mathlib; the formalization and the rule tables are available at https://github.com/yokoyama-lab/small-machine-zoo