Infinite time Turing machines
From MaRDI portal
Abstract: We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. The resulting computability theory leads to a notion of computation on the reals and concepts of decidability and semi-decidability for sets of reals as well as individual reals. Every Pi^1_1 set, for example, is decidable by such machines, and the semi-decidable sets form a portion of the Delta^1_2 sets. Our oracle concept leads to a notion of relative computability for reals and sets of reals and a rich degree structure, stratified by two natural jump operators.
Recommendations
- scientific article; zbMATH DE number 1909830
- New Computational Paradigms
- The Length of Infinite Time Turing Machine Computations
- A Survey of Infinite Time Turing Machines
- Logical Approaches to Computational Barriers
- Infinite time Turing machines with only one tape
- Infinite-time Turing machines and Borel reducibility
- Space and time complexity for infinite time Turing machines
- Cardinal-recognizing infinite time Turing machines
- Weaker variants of infinite time Turing machines
Cites work
Cited in
(only showing first 100 items - show all)- Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems
- Infinite time extensions of Kleene's \({\mathcal O}\)
- Post's problem for ordinal register machines: an explicit approach
- Post's problem for supertasks has both positive and negative solutions
- P NP for infinite time Turing machines
- Preface: Super-recursive algorithms and hypercomputation.
- Super-tasks, accelerating Turing machines and uncomputability
- The modal argument for hypercomputing minds
- Hypercomputation by definition
- A representation of recursively enumerable sets through Horn formulas in higher recursion theory
- Recognizable sets and Woodin cardinals: computation beyond the constructible universe
- Ordinal computability. An introduction to infinitary machines
- Supertasks do not increase computational power
- Classical and new paradigms of computation and their complexity hierarchies. Papers of the conference ``Foundations of the formal sciences III, Vienna, Austria, September 21-24, 2001.
- Admissibles in gaps
- Koepke machines and satisfiability for infinitary propositional languages
- The recognizability strength of infinite time Turing machines with ordinal parameters
- Infinite time busy beavers
- Clocked population protocols
- Characterizations of ITBM-computability. II
- Taming Koepke's zoo. II: Register machines
- Exploring mathematical objects from custom-tailored mathematical universes
- Clockability for ordinal Turing machines
- The lost melody theorem for infinite time Blum-Shub-Smale machines
- Descriptive set theory, from Cantor to Wadge and beyond
- Between Turing and Kleene
- Decision times of infinite computations
- Surreal Blum-Shub-Smale machines
- Higher type recursion for transfinite machine theory
- The basic theory of infinite time register machines
- Weaker variants of infinite time Turing machines
- On the classification of vertex-transitive structures
- On TAE machines and their computational power
- Cofinally invariant sequences and revision
- Higher randomness and forcing with closed sets
- Infinite computations with random oracles
- On fixpoint arithmetic and infinite time Turing machines
- The computational power of infinite time Blum-Shub-Smale machines
- Rethinking revision
- The distribution of ITRM-recognizable reals
- The computational strengths of -tape infinite time Turing machines
- Minimality considerations for ordinal computers modeling constructibility
- Bounding lemmata for non-deterministic halting times of transfinite Turing machines
- A new Gödelian argument for hypercomputing minds based on the busy beaver problem
- The case for hypercomputation
- The many forms of hypercomputation
- Computational power of infinite quantum parallelism
- Revision sequences and computers with an infinite amount of time
- The myth of `the myth of hypercomputation'
- Some transfinite generalisations of Gödel's incompleteness theorem
- Towards a theory of infinite time Blum-Shub-Smale machines
- Some observations on truth hierarchies
- Hypermachines
- A note on accelerated Turing machines
- ITTMs with feedback
- A Computational Approach to an Alternative Working Environment for the Constructible Universe
- Multi-resolution cellular automata for real computation
- On revision operators
- Relativistic Computers and Transfinite Computation
- Generalized effective reducibility
- ITRM-recognizability from random oracles
- Turing Computations On Ordinals
- Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals
- An Enhanced Theory of Infinite Time Register Machines
- Parameter-free uniformisation
- Ultrafilter and Non-standard Turing Machines
- Hyperloops do not threaten the notion of an effective procedure
- Infinite-time Turing machines and Borel reducibility
- Ordinal computability
- Ultimate truth vis-à-vis stable truth
- 2006 Annual Meeting of the Association for Symbolic Logic
- A Survey of Infinite Time Turing Machines
- Is P = PSPACE for Infinite Time Turing Machines?
- scientific article; zbMATH DE number 3924764 (Why is no real title available?)
- scientific article; zbMATH DE number 4005621 (Why is no real title available?)
- Computation as an unbounded process
- Pf ≠ NPf for almost all f
- Nonlinear phenomena in spaces of algorithms
- Building Infinite Machines
- The Length of Infinite Time Turing Machine Computations
- Eventually infinite time Turing machine degrees: infinite time decidable reals
- scientific article; zbMATH DE number 1749140 (Why is no real title available?)
- RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY
- Deciding Arithmetic Using SAD Computers
- 2003 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquim '03
- scientific article; zbMATH DE number 1839449 (Why is no real title available?)
- scientific article; zbMATH DE number 1909826 (Why is no real title available?)
- Ideal negative conceivability and the halting problem
- Tree representations via ordinal machines
- The epistemology of computer-mediated proofs
- Measure-theoretic uniformity and the Suslin functional
- Characterisations of variant transfinite computational models: Infinite time Turing, ordinal time Turing, and Blum–Shub–Smale machines
- Finiteness and computation in toposes
- The significance of relativistic computation for the philosophy of mathematics
- Reachability for infinite time Turing machines with long tapes
- scientific article; zbMATH DE number 7204368 (Why is no real title available?)
- The classification of countable models of set theory
- Physical computational complexity and first-order logic
- Genericity and randomness with ITTMs
- Small steps toward hypercomputation via infinitary machine proof verification and proof generation
This page was built for publication: Infinite time Turing machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4508248)
