2023/02/13 by Lorenzo Galeotti, Galeotti, Lorenzo, Ethan S. Lewis +3
Computer Science · #Cellular Automata and Applications #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2302.06444
openalex publication_date 2023/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Finite Turing computation has a fundamental symmetry between inputs, outputs, programs, time, and storage space. Standard models of transfinite computational break this symmetry; we consider ways to recover it and study the resulting model of computation. This model exhibits the same symmetry as finite Turing computation in universes constructible from a set of ordinals, but that statement is independent of von Neumann-Gödel-Bernays class theory.