On Small Universal Reversible Turing Machines
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
- Quantitative Verification of Infinite-State Networks
- A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata
- Positive-Data Learning of Fixed-Observation Linear MCFGs from Working Binary Presentations
- On the Separability Problem of VASS Reachability Languages
- Exact Accepting-State Spectrum for Reversal of Permutation Automata
- On Word Representations and Embeddings in Complex Matrices