Symmetry for transfinite computability
From MaRDI portal
Publication:6149031
DOI10.1007/978-3-031-36978-0_6arXiv2302.06444OpenAlexW4384788799MaRDI QIDQ6149031FDOQ6149031
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)
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.
Full work available at URL: https://arxiv.org/abs/2302.06444
Recommendations
Cites Work
- Set Theory
- Labyrinth of thought. A history of set theory and its role in modern mathematics.
- Infinite time Turing machines
- Title not available (Why is that?)
- Ordinal machines and admissible recursion theory
- Turing Computations On Ordinals
- Infinite time Turing machines with only one tape
- Realisability for infinitary intuitionistic set theory
- Ordinal computability
- P ≠ NP ∩ co-NP for Infinite Time Turing Machines
- Pf ≠ NPf for almost all f
- Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems
- Ordinal computability. An introduction to infinitary machines
- Logical Approaches to Computational Barriers
- \(P\neq NP\) for infinite time Turing machines
- Introduction to mathematical logic
- Koepke machines and satisfiability for infinitary propositional languages
- Is P = PSPACE for Infinite Time Turing Machines?
- Surreal Blum-Shub-Smale machines
- Space-bounded OTMs and REG ∞
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)
