A1 Refereed original research article in a scientific journal

A physically universal Turing machine



Authors: Salo Ville, Törmä Ilkka

Publisher: Academic Press

Publication year: 2023

Journal: Journal of Computer and System Sciences

Journal name in source: J. Comput. System Sci.

Volume: 132

First page : 16

Last page: 44

ISSN: 0022-0000

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

Web address : https://doi.org/10.1016/j.jcss.2022.08.003

Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/177553931


Abstract

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.


Downloadable publication

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.


Last updated on 2025-27-03 at 21:40