Representation of left-computable \(\varepsilon \)-random reals

DOI10.1016/j.jcss.2010.08.001zbMath1223.03023OpenAlexW2097083282WikidataQ57001533 ScholiaQ57001533MaRDI QIDQ716316

Nicholas J. Hay, Frank Stephan, Cristian S. Calude

Publication date: 28 April 2011

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.08.001

zbMATH Keywords

representabilityPeano arithmetichalting probability\(\varepsilon \)-random real\(\varepsilon \)-universal prefix-free Turing machineleft-computable random reals

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Algorithmic randomness and dimension (03D32)

Related Items (9)

On Oscillation-Free Chaitin h-Random Sequences ⋮ Phase Transition between Unidirectionality and Bidirectionality ⋮ Simplicity via provability for universal prefix-free Turing machines ⋮ CHAITIN’S Ω AS A CONTINUOUS FUNCTION ⋮ Exact constructive and computable dimensions ⋮ Algorithmic information theory and its statistical mechanical interpretation ⋮ Finite state complexity ⋮ Searching for shortest and least programs ⋮ Finite state incompressible infinite sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• Kolmogorov complexity and Hausdorff dimension
• On partial randomness
• Randomness and Recursive Enumerability
• Partial Randomness and Dimension of Recursively Enumerable Reals
• Every computably enumerable random real is provably computably enumerable random
• Algorithmic Information Theory
• A Theory of Program Size Formally Identical to Information Theory
• Recursively enumerable reals and Chaitin \(\Omega\) numbers

This page was built for publication: Representation of left-computable \(\varepsilon \)-random reals