Computing a Glimpse of Randomness

DOI10.1080/10586458.2002.10504481zbMath1117.68385arXivnlin/0112022OpenAlexW2591578264MaRDI QIDQ5472034

Michael J. Dinneen, Chi-Kou Shu, Cristian S. Calude

Publication date: 14 June 2006

Published in: Experimental Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

halting problemalgorithmic randomnessChaitin Omega number

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (7)

A Program-Size Complexity Measure for Mathematical Problems and Conjectures ⋮ Computer Runtimes and the Length of Proofs ⋮ Nonnormality of Stoneham constants ⋮ Searching for shortest and least programs ⋮ Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega ⋮ The complexity of the four colour theorem ⋮ INDUCTIVE COMPLEXITY MEASURES FOR MATHEMATICAL PROBLEMS

Cites Work

• Classical recursion theory. The theory of functions and sets of natural numbers
• Chaitin \(\Omega\) numbers, Solovay machines, and Gödel incompleteness.
• Randomness and Recursive Enumerability
• Algorithmic Information Theory
• A Theory of Program Size Formally Identical to Information Theory
• The definition of random sequences
• A characterization of c. e. random reals
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Computing a Glimpse of Randomness