跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.00153 · v2

On Small Universal Reversible Turing Machines

首次提交 2026-10-30 15:19
版本更新 2026-11-16 21:09
雷达观测 2026-11-17 17:11
arXiv ↗PDF ↗

摘要

A reversible Turing machine (RTM) is a Turing machine in which every instantaneous description has at most one predecessor. Writing URTM(m,n)\mathrm{URTM}(m,n) for a universal RTM with mm states and nn symbols, we construct URTM(3,600)\mathrm{URTM}(3,600), URTM(4,38)\mathrm{URTM}(4,38), URTM(5,36)\mathrm{URTM}(5,36), URTM(6,28)\mathrm{URTM}(6,28), URTM(7,26)\mathrm{URTM}(7,26), URTM(8,21)\mathrm{URTM}(8,21), URTM(9,8)\mathrm{URTM}(9,8), URTM(10,7)\mathrm{URTM}(10,7), and URTM(85,2)\mathrm{URTM}(85,2); 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 O(mn2)O(mn^2) symbols instead of O(m2n3)O(m^2n^3). URTM(10,7)\mathrm{URTM}(10,7) comes from merging two states of Morita's URTM(13,7)\mathrm{URTM}(13,7), recording the difference in tags on the tape cells, and then merging symbols, three times; one more such step gives URTM(9,8)\mathrm{URTM}(9,8). 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

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-16 21:09 · 最新观测版本

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 URTM(m,n)\mathrm{URTM}(m,n) for a universal RTM with mm states and nn symbols, we construct URTM(3,600)\mathrm{URTM}(3,600), URTM(4,38)\mathrm{URTM}(4,38), URTM(5,36)\mathrm{URTM}(5,36), URTM(6,28)\mathrm{URTM}(6,28), URTM(7,26)\mathrm{URTM}(7,26), URTM(8,21)\mathrm{URTM}(8,21), URTM(9,8)\mathrm{URTM}(9,8), URTM(10,7)\mathrm{URTM}(10,7), and URTM(85,2)\mathrm{URTM}(85,2); 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 O(mn2)O(mn^2) symbols instead of O(m2n3)O(m^2n^3). URTM(10,7)\mathrm{URTM}(10,7) comes from merging two states of Morita's URTM(13,7)\mathrm{URTM}(13,7), recording the difference in tags on the tape cells, and then merging symbols, three times; one more such step gives URTM(9,8)\mathrm{URTM}(9,8). 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.

查看此版本解读 →查看此版本原文 ↗