CS Paper Radar

On Small Universal Reversible Turing Machines

T. Yokoyama

cs.FL cs.LO ·submitted 2026-10-30 07:19 UTC · v1
code/data

Abstract

A reversible Turing machine (RTM) is a Turing machine in which every instantaneous description has at most one predecessor. Writing URTM(m,n) for a universal RTM with m states and n symbols, we construct URTM(3,600), URTM(4,41), URTM(5,37), URTM(6,30), URTM(7,28), URTM(8,21), and URTM(85,2); each of them has fewer states or fewer symbols than each of the nine URTMs in Morita's book (2017). They 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 O(mn^2) symbols instead of O(m^2n^3). 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.

Comment
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

Closest papers

Nearest neighbours by meaning across the whole index.

Turn Complexity and Bounded Languages

cs.FL ·2026-08-25 ·Giovanni Pighizzini
publishedtheoryhot direction similarity 0.61
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

A turn or reversal in a computation of a pushdown automaton is a switch from a phase in which the height of the pushdown store increases to a phase in which it decreases. Given a pushdown automaton, we first consider, for each string in its language, the minimum number of turns made in accepting computations (weak measure). We prove that it is decidable whether a pushdown automaton accepts a bounded language in a constant number of turns and whether it accepts a bounded language in k turns, for any given k>=0. This is in contrast to the general case, in which these problems are known to be undecidable, with the exception of acceptance in 0 turns, which is decidable. Furthermore, we prove that when the number of turns sufficient to accept a bounded language is not limited by any constants, it linearly grows with respect to the input length. Also this is in contrast with the general case where, for each nonnegative k, there exists a language for which the number of turns necessary and sufficient is of the order of log^(k), the k times composition of the logarithm with itself. We also prove that, when the costs of all accepting computations are taken into account (accept measure), a linear lower bound for the number of turns, if not limited by any constants, holds even removing the restriction to bounded languages.

0.43

A 120-State Binary Turing Machine Equivalent to the Riemann Hypothesis

cs.FL ·2026-09-23 ·Joseph M. Shunia
unusual similarity 0.60
Abstract

We construct an explicit deterministic one-tape, two-symbol Turing machine with 120 working states whose blank-tape computation halts if and only if the Riemann hypothesis is false. The machine uses the same binary blank-tape model and state-counting convention as the widely cited 744-state Matiyasevich-O'Rear-Aaronson construction. The reduction from 744 to 120 working states removes 624 states, or 83.87%. Subject to independent end-to-end verification, our machine is a new state-count record for the Riemann hypothesis.

0.34

Symmetric two-counter machines

cs.FL ·2026-10-16 ·Krzysztof Jaros, Łukasz Kamiński, Maja Kądziołka, Sławomir Lasota
theory similarity 0.59
Abstract

Counter machines are a particularly simple, Turing-complete model of computation. We study the expressive power of nondeterministic 2-counter machines which are symmetric, in that their set of update transitions is invariant under swapping of counters. Our model is an extension of symmetric 2-VASS, in that we allow modifying both counters within a single transition. As the main result we demonstrate a dramatic impact of symmetry: we show that symmetric 2-counter machines are not Turing-complete, by proving decidability of their reachability problem. We conjecture that the decidability extends to machines with 3 or more counters that are symmetric, meaning the set of update transitions is invariant under any permutation of counters. We leave this problem open for machines with 3 and more counters, while identifying a frontier of the impact of symmetry: we prove undecidability for 3-counter machines invariant under the cyclic permutation group of order 3.

0.22

Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable

cs.FL cs.LO ·2026-10-29 ·Mingkun Xiao, Yixuan Sun
theory similarity 0.59
Abstract · 31 pages, 3 figures. Rocq artifact: https://doi.org/10.5281/zenodo.23734555

Higher-order recursion schemes (HORS) are finite, simply typed recursive programs that generate potentially infinite trees. Their monadic second-order model-checking problem is decidable. We prove that tree equivalence of deterministic HORS is undecidable and, more precisely, $Π^0_1$-complete under total computable many-one reductions. The lower bound holds for safe, productive schemes of order at most four over the fixed ranked alphabet $Σ_2=\{e:0,d:2\}$, consisting of one nullary and one binary symbol. Adapting the counter-guard witness of Boiret, Piorkowski, and Schmude, we generate all candidate executions of a two-counter machine by producing both continuations at every counter test. An integer weight is nonzero exactly on legal prefixes. Functions at fixed simple types represent the polynomial of growing degree. A shift recurrence updates them without storing a separate step counter, allowing the witness to be implemented by safe applicative HORS rules. At candidate halts, the intermediate schemes generate unary observation subtrees whose lengths encode the two natural-number components of the signed weight. Invalid candidates give matching observations; a legal halt produces a finite discrepancy. Fixed constructor contexts encode these intermediate trees over $Σ_2$. For the upper bound, a finite monotone semantics decides head convergence and supports an algorithm computing exact tree prefixes at any prescribed finite depth, including positions labelled $\bot$.

0.32

A Factor-Two Lower Bound for Complementing Two-Way Deterministic Finite Automata

cs.FL cs.CC ·2026-10-10 ·Sudais Arif
theoryhot direction similarity 0.58
Abstract · 18 pages, 1 figure

For every $n\ge22$, we construct a language over a fixed three-letter alphabet whose two-way deterministic state complexity is $n$ and whose complement has state complexity $2n$. Acceptance is at the left endmarker, and infinite computations reject. The lower bound holds for arbitrary deterministic recognizers. The proof uses the group of transformations induced by the witness to constrain the behavior of a smaller recognizer, then derives a contradiction from a permutation query problem. A matching halting complement follows from a $2n$-state construction for sources whose destination states determine the direction of each transition. Splitting states by incoming direction gives a $2n+2b$ upper bound for general sources, where $b$ counts states entered in both directions. In the acceptance-anywhere model of Geffert, Mereghetti, and Pighizzini, the same family has exact complexities $N$ and $2N-1$ for every $N\ge23$.

0.39

Relative Prime Factorization and Finite-State Presentations under Fixed Finite-Monoid Observation

cs.FL cs.LG ·2026-09-03 ·Takayuki Kuriyama
similarity 0.57
Abstract · 47 pages; reproducible verification code and a machine-readable certificate for the 36-element witness are available via the fixed GitHub sn…

Let $L\subseteqΣ^*$ and fix a morphism $h:Σ^*\to M$ into a finite monoid. We study exact factorization and canonical presentation in the relative syntactic congruence $θ_{L,h}:=\equiv_L\cap\ker h$. We separate unique factorization from finite direct presentation. An exhaustively computer-checked $36$-element quotient has a unique exact prime factorization for every live non-unit class, yet its valid prime-return rules contain an infinite family, so unique factorization does not imply the finite relative presentation property (FRP), even for a finite quotient. We lift the same defect to a nonregular context-free language with an infinite relative quotient and finite prime spectrum. To isolate the obstruction, we introduce the finite-state relative presentation property (FSRP), in which canonical valid right-hand-side languages are represented by finite residual controllers, and prove $\mathrm{FRP}\subsetneq\mathrm{FSRP}$. We then introduce prime-target left-division determinism (PTLD), which implies unique exact factorization, tail exactness, tail determinism, and a quadratic bound on valid rules. A nonregular deterministic context-free example with a finite group observer satisfies PTLD while lying outside every fixed $(k,\ell)$-substitutable class. Finally, for fixed $h$ we give a strong positive-data learner for the canonical PTLD presentation with polynomial-time hypothesis updates and a finite characteristic sample, together with a limit reconstruction of the canonical FSRP controller from weakly behaviorally correct CFG-valued learners.

0.30

Unconditional Separation between LL and CLL

cs.CC ·2026-10-11 ·Shubham Bhardwaj
publishedtheory similarity 0.57
Abstract · 11 pages. v2: fixed an error in the upper bound concerning the endmarkers of the catalytic tape; thanks to András Salamon for pointing it ou…

Catalytic computation involves the study of Turing machines that are provided an additional catalytic tape (with arbitrary content) that the machine may use while ensuring that the tape contents are restored at the end of the computation. Although it is known that catalytic log-space machines are at least as powerful as non-deterministic log-space (and more), we do not have unconditional asymptotic separations. In this work, we prove an unconditional separation between a deterministic space complexity class and its catalytic counterpart. More precisely, at the doubly logarithmic scale, we show that catalytic Turing machines can provably compute more languages than standard deterministic doubly-logarithmic space machines. The separation is witnessed by the unary language $\mathrm{POW2} = \{1^n : n \text{ is a power of two}\}$. We construct a catalytic Turing machine that uses $O(\log \log n)$ bits of space and $O(\log n)$ bits of catalytic tape to decide $\mathrm{POW2}$, whereas any standard deterministic Turing machine requires $Ω(\log n)$ space to decide it.

0.30

Reconfiguration of Time-Bounded Descriptions

cs.CC cs.DM ·2026-11-06 ·Dimitrios Myrisiotis
similarity 0.57
Abstract · 50 pages

Time-bounded Kolmogorov complexity measures a string by the length of its shortest program that prints it within a deadline. An adjunction-universal machine (Bauwens, Kozachinskiy, and Shen, arXiv, 2025) is a Turing machine that simulates every Turing machine $M$ on every input $z$ with polynomial overhead when given a code of $M$, computable from $M$ in polynomial time, followed by $z$ unchanged. Any two adjunction-universal machines give the same measure up to an additive constant and a polynomial change of the deadline. However, this measure records only the shortest program for a string. We study all programs of one length that print a string within one deadline, join two of them when they differ in one bit, and ask when this graph is connected. Fix any adjunction-universal machine. For almost all $m$-bit strings and every deadline beyond some polynomial, the graph is disconnected at program length $m+O(1)$ and has at least $2^{m-O(1)}$ components at length $2m+3$. In contrast, we build an adjunction-universal machine in which every such graph is connected or empty, at every deadline, once the program length reaches a computable threshold that is at most exponential in the length of the string. Exponential thresholds are unavoidable: for every adjunction-universal machine with such thresholds and every large $m$, more than three quarters of the $m$-bit strings need a threshold exponential in $m$. For our machine, above the threshold, every program for the string is within three bit flips of a connected set of fastest programs for the string, along a path inside the graph, at every deadline by which that program halts. For this machine, deciding whether two given programs are connected in this graph is $\mathsf{PSPACE}$-complete when the input is the string, the deadline in unary and the two programs; for each fixed string it takes polynomial time.

0.29