A physically universal Turing machine




Salo Ville, Törmä Ilkka

PublisherAcademic Press

2023

Journal of Computer and System Sciences

J. Comput. System Sci.

132

16

44

0022-0000

DOIhttps://doi.org/10.1016/j.jcss.2022.08.003

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

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



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.


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