Symmetry for transfinite computability

DOI10.1007/978-3-031-36978-0_6arXiv2302.06444OpenAlexW4384788799MaRDI QIDQ6149031

Lorenzo Galeotti, Ethan S. Lewis, Benedikt Loewe

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems
• Ordinal machines and admissible recursion theory
• \(P\neq NP\) for infinite time Turing machines
• Ordinal computability. An introduction to infinitary machines
• Koepke machines and satisfiability for infinitary propositional languages
• Surreal Blum-Shub-Smale machines
• Realisability for infinitary intuitionistic set theory
• Infinite Time Turing Machines With Only One Tape
• Turing Computations On Ordinals
• P ≠ NP ∩ co-NP for Infinite Time Turing Machines
• Ordinal Computability
• Is P = PSPACE for Infinite Time Turing Machines?
• Pf ≠ NPf for almost all f
• Infinite time Turing machines
• Set Theory
• Space-bounded OTMs and REG ∞
• Logical Approaches to Computational Barriers

This page was built for publication: Symmetry for transfinite computability