The basic theory of infinite time register machines

DOI10.1007/s00153-009-0167-xzbMath1184.03044MaRDI QIDQ2267751

Gregor Weckbecker, Peter Koepke, Tim Fischbach, Merlin Carl, Miriam Nasfi, Russell G. Miller

Publication date: 2 March 2010

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00153-009-0167-x

zbMATH Keywords

register machine; hypercomputation; infinitary computation; ordinal computability

Mathematics Subject Classification ID

03D10: Turing machines and related notions

03D60: Computability and recursion theory on ordinals, admissible sets, etc.

Related Items

RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY, Randomness and degree theory for infinite time register machines1, Recognizable sets and Woodin cardinals: computation beyond the constructible universe, The distribution of ITRM-recognizable reals, OPTIMAL RESULTS ON RECOGNIZABILITY FOR INFINITE TIME REGISTER MACHINES, Discrete Transfinite Computation, A Generalised Dynamical System, Infinite Time Register Machines, and $\Pi^1_1$ -CA0, $$ITRM$$-Recognizability from Random Oracles

Cites Work

• Register computations on ordinals
• Ordinal machines and admissible recursion theory
• Minimality considerations for ordinal computers modeling constructibility
• Turing Computations On Ordinals
• An Enhanced Theory of Infinite Time Register Machines
• Infinite time Turing machines
• Post’s Problem for Ordinal Register Machines
• The Complexity of Quickly ORM-Decidable Sets
• The fine structure of the constructible hierarchy
• Logical Approaches to Computational Barriers