On Small Universal Reversible Turing Machines

arXiv:2611.00153 · cs.FL, cs.LO · Submitted 2026-10-30 · Read on arXiv

cs.FL, cs.LO

Submitted: 2026-10-30

Updated: 2026-11-16

Comments: 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

Code: https://github.com/yokoyama-lab/small-machine-zoo

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

Related papers