Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals

zbMATH Open1329.03075arXiv1101.1864MaRDI QIDQ3464656FDOQ3464656

Authors: Samuel Coskey, Joel David Hamkins 

Publication date: 27 January 2016

Abstract: We describe the basic theory of infinite time Turing machines and some recent developments, including the infinite time degree theory, infinite time complexity theory, and infinite time computable model theory. We focus particularly on the application of infinite time Turing machines to the analysis of the hierarchy of equivalence relations on the reals, in analogy with the theory arising from Borel reducibility. We define a notion of infinite time reducibility, which lifts much of the Borel theory into the class $$ in a satisfying way.

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

Recommendations

• Infinite-time Turing machines and Borel reducibility
• Infinite time decidable equivalence relation theory
• A Survey of Infinite Time Turing Machines
• Infinite time Turing machines
• Eventually infinite time Turing machine degrees: infinite time decidable reals

zbMATH Keywords

infinite-time Turing machinesinfinite-time reducibility

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Descriptive set theory (03E15) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10) Other degrees and reducibilities in computability and recursion theory (03D30)

Cited In (12)

• Eventually infinite time Turing machine degrees: infinite time decidable reals
• Infinite time decidable equivalence relation theory
• A Survey of Infinite Time Turing Machines
• Infinite-time Turing machines and Borel reducibility
• On fixpoint arithmetic and infinite time Turing machines
• Is P = PSPACE for Infinite Time Turing Machines?
• Bounding lemmata for non-deterministic halting times of transfinite Turing machines
• Infinite time extensions of Kleene's \({\mathcal O}\)
• Infinite time computable model theory
• Title not available (Why is that?)
• Parameter-free uniformisation
• Production en temps réel et complexité de structure de suites infinies

This page was built for publication: Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals

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