Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems

DOI10.1016/j.tcs.2008.09.050zbMath1160.68013OpenAlexW2050766716WikidataQ55968655 ScholiaQ55968655MaRDI QIDQ1004086

J. Martínez

Publication date: 2 March 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.09.050

zbMATH Keywords

admissibilitytransfinite computationcomputation on the realsconstructibility theory

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Turing machines and related notions (03D10)

Related Items

Decision times of infinite computations, SOME OBSERVATIONS ON TRUTH HIERARCHIES, RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY, Discrete Transfinite Computation, Symmetry for transfinite computability, The computational strengths of \(\alpha\)-tape infinite time Turing machines, Hypermachines, Admissibles in gaps, The recognizability strength of infinite time Turing machines with ordinal parameters, Infinite time busy beavers, Taming Koepke's zoo. II: Register machines, Characterisations of variant transfinite computational models: Infinite time Turing, ordinal time Turing, and Blum–Shub–Smale machines, Clockability for ordinal Turing machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptive set theory
• Classical recursion theory. The theory of functions and sets of natural numbers
• Post's problem for supertasks has both positive and negative solutions
• 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.
• Infinite Time Turing Machines With Only One Tape
• Revision Sequences and Computers with an Infinite Amount of Time
• Recursive Functionals and Quantifiers of Finite Types I
• P ≠ NP ∩ co-NP for Infinite Time Turing Machines
• Parameter-free uniformisation
• The truth is never simple
• A fine hierarchy of partition cardinals
• The Length of Infinite Time Turing Machine Computations
• Infinite time Turing machines
• Eventually infinite time Turing machine degrees: infinite time decidable reals
• Deciding Arithmetic Using SAD Computers
• Recent Advances in Ordinal Analysis: Π¹₂— CA and Related Systems
• The Extent of Computation in Malament–Hogarth Spacetimes
• The fine structure of the constructible hierarchy
• New Computational Paradigms
• Set-theoretic absoluteness and the revision theory of truth
• Non-Turing computations via Malament--Hogarth space-times