The computational strengths of -tape infinite time Turing machines

DOI10.1016/J.APAL.2014.04.016MaRDI QIDQ2453073zbMATH OpenOpenAlexFDO

Authors Benjamin G. Rin

Publication date 6 June 2014

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2014.04.016

zbMATH Keywords

infinite-time Turing machineordinal computabilitysupertasktransfinite computation

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Computation over the reals, computable analysis (03D78)

Recommendations

• Weaker variants of infinite time Turing machines
• Infinite time Turing machines with only one tape
• Cardinal-recognizing infinite time Turing machines
• The Length of Infinite Time Turing Machine Computations
• Infinite time Turing machines

Cites work

• Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems
• scientific article; zbMATH DE number 194101 (Why is no real title available?)
• Infinite time extensions of Kleene's \({\mathcal O}\)
• Infinite time Turing machines
• Infinite time Turing machines with only one tape
• Logical Approaches to Computational Barriers
• Ordinal computability
• Ordinal machines and admissible recursion theory
• Set theory. An introduction to independence proofs
• The Length of Infinite Time Turing Machine Computations
• Towards a theory of infinite time Blum-Shub-Smale machines
• Turing Computations On Ordinals

Cited in

(14)

• Taming Koepke's zoo
• Koepke machines and satisfiability for infinitary propositional languages
• Towards computable analysis on the generalised real line
• Realisability for infinitary intuitionistic set theory
• Characterisations of variant transfinite computational models: Infinite time Turing, ordinal time Turing, and Blum–Shub–Smale machines
• Reachability for infinite time Turing machines with long tapes
• On the Weihrauch degree of the additive Ramsey theorem
• Hilbert's tenth problem for term algebras with a substitution operator
• Complemented subsets and Boolean-valued, partial functions
• Defining long words succinctly in FO and MSO
• On the first-order parts of problems in the Weihrauch degrees
• Algorithmically random series
• Ideal presentations and numberings of some classes of effective quasi-Polish spaces
• Lower bounds on () and other properties of -register machines

This page was built for publication: The computational strengths of \(\alpha\)-tape infinite time Turing machines

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