Randomness and degree theory for infinite time register machines1

DOI10.3233/COM-160055zbMath1401.03078arXiv1508.04618MaRDI QIDQ5740208

Merlin Carl

Publication date: 25 July 2016

Published in: Computability (Search for Journal in Brave)

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

zbMATH Keywords

forcingdegree theoryalgorithmic randomnessordinal computabilityinfinite time register machines

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Turing machines and related notions (03D10) Other aspects of forcing and Boolean-valued models (03E40) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Algorithmic randomness and dimension (03D32)

Related Items (1)

RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY

Cites Work

• The basic theory of infinite time register machines
• OPTIMAL RESULTS ON RECOGNIZABILITY FOR INFINITE TIME REGISTER MACHINES
• High and low Kleene degrees of coanalytic sets
• Turing Computations On Ordinals
• Infinite time Turing machines
• An extension of the recursively enumerable Turing degrees
• Randomness via effective descriptive set theory

This page was built for publication: Randomness and degree theory for infinite time register machines1