Random reals as measures of natural open sets

DOI10.1016/J.TCS.2015.04.009MaRDI QIDQ2346372zbMATH OpenOpenAlexFDO

Authors Claude Sureson

Publication date 1 June 2015

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

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

zbMATH Keywords

algorithmic randomnessarithmetical hierarchyCantor space

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Review text

The author proposes a general method to define \(n\)-random reals for natural numbers \(n\geq 2\). He defines sets of finite words over the alphabet \(\{0,1\}\) in the arithmetical hierarchy which generate open subsets of Cantor space whose measure is \(n\)-random. He investigates two approaches: {\parindent=0,5cm \begin{itemize}\item[--] the first one focusing on open subsets \(W\cdot \{0,1\}^\omega\) of Cantor space by defining the generating sets \(W\subseteq \{0,1\}^*\) of finite words in a generalised Becher-Chaitin style see: [\textit{V. Becher} and \textit{G. Chaitin}, Fundam. Inform. 51, No. 4, 325--338 (2002; Zbl 1011.68042)], and \item[--] the second one converting arguments of completeness from classical recursion theory thus avoiding the use of machines. \end{itemize}}

Recommendations

• \({\Pi}_1^1\)-Martin-Löf random reals as measures of natural open sets
• Measures and their random reals
• Effectively closed sets of measures and randomness
• Random reals and Lipschitz continuity
• A characterization of c. e. random reals
• scientific article; zbMATH DE number 3943806
• On the Continuity and Absolute Continuity of Random Closed Sets
• Relative randomness and real closed fields
• Perfect sets of random reals
• Partial Randomness and Dimension of Recursively Enumerable Reals

Cites work

• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic randomness and complexity.
• Classical recursion theory. The theory of functions and sets of natural numbers.
• Classical recursion theory. Vol. II
• Computability and randomness
• Degrees of Unsolvability. (AM-55)
• Descriptive set theory
• From index sets to randomness in ∅ⁿ: random reals and possibly infinite computations part II
• scientific article; zbMATH DE number 1665444 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1886067 (Why is no real title available?)
• Random reals and possibly infinite computations Part I: Randomness in ∅′

Cited in

(7)

• \({\Pi}_1^1\)-Martin-Löf random reals as measures of natural open sets
• Effectively approximating measurable sets by open sets
• scientific article; zbMATH DE number 2086685 (Why is no real title available?)
• Random numbers as probabilities of machine behavior
• Measures and their random reals
• Algorithmic Randomness of Closed Sets
• scientific article; zbMATH DE number 961049 (Why is no real title available?)

This page was built for publication: Random reals as measures of natural open sets

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