Random reals and possibly infinite computations Part I: Randomness in ∅′

DOI10.2178/jsl/1122038919zbMath1089.03037OpenAlexW1969078420WikidataQ61927044 ScholiaQ61927044MaRDI QIDQ5718694

Serge Grigorieff, Verónica Becher

Publication date: 16 January 2006

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

Full work available at URL: https://doi.org/10.2178/jsl/1122038919

zbMATH Keywords

program-size complexityinfinite computationmonotone Turing machinerandom real in \(0'\)

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Turing machines and related notions (03D10)

Related Items

Kolmogorov complexities \(K_{\max}\), \(K_{\min}\) on computable partially ordered sets, Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations, \({\Pi}_1^1\)-Martin-Löf random reals as measures of natural open sets, Randomness and universal machines, Differences of halting probabilities, Randomness and uniform distribution modulo one, CHAITIN’S Ω AS A CONTINUOUS FUNCTION, Preface, Random reals à la Chaitin with or without prefix-freeness, Random numbers as probabilities of machine behavior, Wadge hardness in Scott spaces and its effectivization, From index sets to randomness in ∅ⁿ: random reals and possibly infinite computations part II, Calibrating Randomness, Random reals as measures of natural open sets

Cites Work

• Unnamed Item
• Unnamed Item
• Descriptive set theory
• Adherences of languages
• Algorithmic entropy of sets
• Presentations of computably enumerable reals.
• Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations
• Process complexity and effective random tests
• Randomness, Computability, and Density
• The topological structure of adherences of regular languages
• A Theory of Program Size Formally Identical to Information Theory
• The definition of random sequences