2020/03/20 by Ville Salo, Salo, Ville, Ilkka Törmä +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #37B50 #68Q45 #Cellular Automata and Applications #Computability, Logic, AI Algorithms #DNA and Biological Computing #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)
paper · pdf · doi:10.48550/arxiv.2003.10328
openalex publication_date 2020/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.