Infinite time Turing machines

DOI10.2307/2586556zbMath0963.03064arXivmath/9808093OpenAlexW2571490773WikidataQ56813205 ScholiaQ56813205MaRDI QIDQ4508248

Andy Lewis, Joel David Hamkins

Publication date: 18 June 2001

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/9808093

zbMATH Keywords

decidabilityTuring machinecomputabilitylimit ordinalcomputation on realsmodel for supertasks-computations with infinitely many stepstransfinite time

Mathematics Subject Classification ID

Related Items (83)

Higher randomness and forcing with closed sets ⋮ On revision operators ⋮ Eventually infinite time Turing machine degrees: infinite time decidable reals ⋮ Some Transfinite Generalisations of Gödel’s Incompleteness Theorem ⋮ Descriptive set theory, from Cantor to Wadge and beyond ⋮ Between Turing and Kleene ⋮ Decision times of infinite computations ⋮ Generalized Effective Reducibility ⋮ On fixpoint arithmetic and infinite time Turing machines ⋮ $$ITRM$$-Recognizability from Random Oracles ⋮ The computational power of infinite time Blum-Shub-Smale machines ⋮ SOME OBSERVATIONS ON TRUTH HIERARCHIES ⋮ RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY ⋮ A representation of recursively enumerable sets through Horn formulas in higher recursion theory ⋮ Output concepts for accelerated Turing machines ⋮ A broader view on the limitations of information processing and communication by nature ⋮ Rethinking revision ⋮ Discrete Transfinite Computation ⋮ An Enhanced Theory of Infinite Time Register Machines ⋮ Recognizable sets and Woodin cardinals: computation beyond the constructible universe ⋮ A constructive picture of Noetherian conditions and well quasi-orders ⋮ Symmetry for transfinite computability ⋮ All melodies are lost -- recognizability for weak and strong \(\alpha \)-register machines ⋮ Computation as an unbounded process ⋮ The classification of countable models of set theory ⋮ Unnamed Item ⋮ The distribution of ITRM-recognizable reals ⋮ The computational strengths of \(\alpha\)-tape 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 ⋮ Ideal negative conceivability and the halting problem ⋮ Register computations on ordinals ⋮ Physical Computational Complexity and First-order Logic ⋮ Hyperloops Do Not Threaten the Notion of an Effective Procedure ⋮ Infinite-Time Turing Machines and Borel Reducibility ⋮ Ordinal Computability ⋮ Minimality considerations for ordinal computers modeling constructibility ⋮ Bounding lemmata for non-deterministic halting times of transfinite Turing machines ⋮ Supertasks do not increase computational power ⋮ ULTIMATE TRUTHVIS-À-VISSTABLE TRUTH ⋮ Randomness and degree theory for infinite time register machines1 ⋮ An injection from the Baire space to natural numbers ⋮ 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 ⋮ The basic theory of infinite time register machines ⋮ A new Gödelian argument for hypercomputing minds based on the busy beaver problem ⋮ 2006 Annual Meeting of the Association for Symbolic Logic ⋮ The case for hypercomputation ⋮ The many forms of hypercomputation ⋮ 2003 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquim '03 ⋮ Computational power of infinite quantum parallelism ⋮ Computability on reals, infinite limits and differential equations ⋮ Abstract geometrical computation. III: Black holes for classical and analog computing ⋮ Clocked population protocols ⋮ GENERICITY AND RANDOMNESS WITH ITTMS ⋮ Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems ⋮ Turing Computations On Ordinals ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Epistemology of Computer-Mediated Proofs ⋮ A Computational Approach to an Alternative Working Environment for the Constructible Universe ⋮ Multi-Resolution Cellular Automata for Real Computation ⋮ Weaker variants of infinite time Turing machines ⋮ On the classification of vertex-transitive structures ⋮ Taming Koepke's zoo. II: Register machines ⋮ Nonlinear phenomena in spaces of algorithms ⋮ Infinite time extensions of Kleene's \({\mathcal O}\) ⋮ Post's problem for ordinal register machines: an explicit approach ⋮ THE MYTH OF 'THE MYTH OF HYPERCOMPUTATION' ⋮ Measure-theoretic uniformity and the Suslin functional ⋮ Characterisations of variant transfinite computational models: Infinite time Turing, ordinal time Turing, and Blum–Shub–Smale machines ⋮ Exploring mathematical objects from custom-tailored mathematical universes ⋮ A NOTE ON THEORIES FOR QUASI-INDUCTIVE DEFINITIONS ⋮ On TAE machines and their computational power ⋮ The Significance of Relativistic Computation for the Philosophy of Mathematics ⋮ Clockability for ordinal Turing machines ⋮ Cofinally invariant sequences and revision ⋮ The lost melody theorem for infinite time Blum-Shub-Smale machines

Cites Work

• Descriptive set theory
• Unnamed Item

This page was built for publication: Infinite time Turing machines