Metraipolis › archive › dc_6ed3cfc3989a

On Small Universal Reversible Turing Machines — arXiv:2611.00153

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.00153
License (as archived)
CC0-1.0
Archived
2026-11-03T11:46:25.066Z
SHA-256 of the archived text
26b62178387afc353408f9e8bef7dd295e5185f6774cfdc987f49b5097d85005
Stable URL of this page
https://metraipolis.com/documento/dc_6ed3cfc3989a

How to cite

On Small Universal Reversible Turing Machines — arXiv:2611.00153 — arXiv (en), https://arxiv.org/abs/2611.00153 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6ed3cfc3989a (Metraipolis archive dc_6ed3cfc3989a, sha256 26b62178387afc353408f9e8bef7dd295e5185f6774cfdc987f49b5097d85005)
BibTeX
@misc{dc6ed3cfc3989a,
  title = {On Small Universal Reversible Turing Machines — arXiv:2611.00153},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.00153},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6ed3cfc3989a; sha256 26b62178387afc353408f9e8bef7dd295e5185f6774cfdc987f49b5097d85005},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.00153. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.LO, nuovi lavori del giorno).
Categorie arXiv: Formal Languages and Automata Theory (cs.FL) ; Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2611.00153 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:08:07.227Z dalla pagina https://arxiv.org/list/cs.LO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).