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

DOI10.1016/J.TCS.2007.12.014MaRDI QIDQ2482464zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

Recommendations

• Logical Approaches to Computational Barriers
• Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems
• Infinite-time Turing machines and Borel reducibility
• scientific article; zbMATH DE number 522863
• Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals
• New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines
• Non-erasing turing machines: A new frontier between a decidable halting problem and universality
• On the generic undecidability of the halting problem for normalized Turing machines
• scientific article; zbMATH DE number 3995646
• Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines

Cites work

• P NP for infinite time Turing machines
• Countable admissible ordinals and hyperdegrees
• Descriptive set theory
• Elementary induction on abstract structures
• scientific article; zbMATH DE number 194101 (Why is no real title available?)
• scientific article; zbMATH DE number 3494394 (Why is no real title available?)
• Infinite time Turing machines
• P ≠ NP ∩ co-NP for Infinite Time Turing Machines
• The Length of Infinite Time Turing Machine Computations

Cited in

(4)

• Decision times of infinite computations
• Halting time is predictable for large models: a universality property and average-case analysis
• Non-erasing turing machines: A new frontier between a decidable halting problem and universality
• Logical Approaches to Computational Barriers

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

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