A physically universal Turing machine - UTU Tutkimustietojärjestelmä

A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

A physically universal Turing machine

Tekijät: Salo Ville, Törmä Ilkka

Kustantaja: Academic Press

Julkaisuvuosi: 2023

Journal: Journal of Computer and System Sciences

Tietokannassa oleva lehden nimi: J. Comput. System Sci.

Vuosikerta: 132

Aloitussivu: 16

Lopetussivu: 44

ISSN: 0022-0000

DOI: https://doi.org/10.1016/j.jcss.2022.08.003

Verkko-osoite: https://doi.org/10.1016/j.jcss.2022.08.003

Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/177553931

Tiivistelmä

We construct a two-dimensional Turing machine that is physically universal in both the moving tape and moving head model. In particular, it is mixing of all finite orders in both models. We also provide a variant that is physically universal in the moving tape model, but not in the moving head model.

Ladattava julkaisu

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.

1-s2.0-S0022000022000617-main.pdf