Infinite time extensions of Kleene's O

DOI10.1007/S00153-009-0146-2MaRDI QIDQ1031833zbMATH OpenOpenAlexFDO

Authors Ansten Mørch Klev

Publication date 23 October 2009

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://doi.org/10.1007/s00153-009-0146-2

zbMATH Keywords

halting probleminfinite-time Turing computabilityinfinite-time Turing machinesordinal notation systems

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Inductive definability (03D70) Recursive ordinals and ordinal notations (03F15)

Recommendations

• An extension of Kleene's and Ochmański's theorems to infinite traces
• Infinite-time Turing machines and Borel reducibility
• Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals
• Kleene star, subexponentials without contraction, and infinite computations
• Infinite versions of some problems from finite complexity theory
• Infinite time computable model theory
• The Length of Infinite Time Turing Machine Computations
• Decision times of infinite computations
• New Computational Paradigms
• Space and time complexity for infinite time Turing machines

Cites work

• Eventually infinite time Turing machine degrees: infinite time decidable reals
• scientific article; zbMATH DE number 194101 (Why is no real title available?)
• scientific article; zbMATH DE number 3188506 (Why is no real title available?)
• Infinite time Turing machines
• On notation for ordinal numbers
• On the Forms of the Predicates in the Theory of Constructive Ordinals (Second Paper)
• Post's problem for supertasks has both positive and negative solutions
• Recursive well-orderings
• The Length of Infinite Time Turing Machine Computations
• The truth is never simple
• Zur Theorie der konstruktiven Wohlordnungen

Cited in

(13)

• Some observations on infinitary complexity
• Taming Koepke's zoo
• Admissibles in gaps
• Clockability for ordinal Turing machines
• Decision times of infinite computations
• The computational strengths of -tape infinite time Turing machines
• All Linear-Time Congruences for Familiar Operators Part 2: Infinite LTSs
• An Infinite Automaton Characterization of Double Exponential Time
• The Length of Infinite Time Turing Machine Computations
• Eventually infinite time Turing machine degrees: infinite time decidable reals
• scientific article; zbMATH DE number 1390284 (Why is no real title available?)
• Reachability for infinite time Turing machines with long tapes
• New Computational Paradigms

This page was built for publication: Infinite time extensions of Kleene's \({\mathcal O}\)

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