Symmetry for transfinite computability

DOI10.1007/978-3-031-36978-0_6MaRDI QIDQ6149031OpenAlexFDO

Authors Lorenzo Galeotti, Ethan S. Lewis, Benedikt Löwe

Publication date 12 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2302.06444

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of computing (68Qxx)

Abstract: 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"odel-Bernays class theory.

Recommendations

• Infinite time Turing machines
• Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems
• Turing Unbound: Transfinite Computation

Cites work

• scientific article; zbMATH DE number 3531386 (Why is no real title available?)
• Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems
• Infinite time Turing machines
• Infinite time Turing machines with only one tape
• Introduction to mathematical logic
• Is P = PSPACE for Infinite Time Turing Machines?
• Koepke machines and satisfiability for infinitary propositional languages
• Labyrinth of thought. A history of set theory and its role in modern mathematics.
• Logical Approaches to Computational Barriers
• Ordinal computability
• Ordinal computability. An introduction to infinitary machines
• Ordinal machines and admissible recursion theory
• P ≠ NP ∩ co-NP for Infinite Time Turing Machines
• Pf ≠ NPf for almost all f
• Realisability for infinitary intuitionistic set theory
• Set Theory
• Space-bounded OTMs and REG ∞
• Surreal Blum-Shub-Smale machines
• Turing Computations On Ordinals
• \(P\neq NP\) for infinite time Turing machines

This page was built for publication: Symmetry for transfinite computability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6149031)