Bounding lemmata for non-deterministic halting times of transfinite Turing machines

DOI10.1016/j.tcs.2007.12.014zbMath1136.03027OpenAlexW2138885481WikidataQ124817136 ScholiaQ124817136MaRDI QIDQ2482464

Philip D. Welch

Publication date: 16 April 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.12.014

Mathematics Subject Classification ID

Descriptive set theory (03E15) Turing machines and related notions (03D10) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (1)

Decision times of infinite computations

Cites Work

• Unnamed Item
• Unnamed Item
• Descriptive set theory
• Countable admissible ordinals and hyperdegrees
• Elementary induction on abstract structures
• \(P\neq NP\) for infinite time Turing machines
• P ≠ NP ∩ co-NP for Infinite Time Turing Machines
• The Length of Infinite Time Turing Machine Computations
• Infinite time Turing machines

This page was built for publication: Bounding lemmata for non-deterministic halting times of transfinite Turing machines