Computing a Glimpse of Randomness

DOI10.1080/10586458.2002.10504481MaRDI QIDQ5472034zbMATH OpenOpenAlexFDO

Authors 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, https://projecteuclid.org/euclid.em/1057777428, https://eudml.org/doc/53299

zbMATH Keywords

algorithmic randomnesshalting problemChaitin Omega number

Mathematics Subject Classification ID

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

Abstract: A Chaitin Omega number is the halting probability of a universal Chaitin (self-delimiting Turing) machine. Every Omega number is both computably enumerable (the limit of a computable, increasing, converging sequence of rationals) and random (its binary expansion is an algorithmic random sequence). In particular, every Omega number is strongly non-computable. The aim of this paper is to describe a procedure, which combines Java programming and mathematical proofs, for computing the exact values of the first 64 bits of a Chaitin Omega: 0000001000000100000110001000011010001111110010111011101000010000. Full description of programs and proofs will be given elsewhere.

Recommendations

• Chaitin numbers and halting problems
• EXACT APPROXIMATIONS OF OMEGA NUMBERS
• Very Simple Chaitin Machines for Concrete AIT
• scientific article; zbMATH DE number 5252382
• scientific article; zbMATH DE number 1911266

Cites work

• scientific article; zbMATH DE number 1223737 (Why is no real title available?)
• scientific article; zbMATH DE number 736618 (Why is no real title available?)
• scientific article; zbMATH DE number 1136091 (Why is no real title available?)
• scientific article; zbMATH DE number 1548484 (Why is no real title available?)
• scientific article; zbMATH DE number 1390092 (Why is no real title available?)
• scientific article; zbMATH DE number 1418478 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• A characterization of c. e. random reals
• Algorithmic Information Theory
• Chaitin numbers, Solovay machines, and Gödel incompleteness.
• Classical recursion theory. The theory of functions and sets of natural numbers
• Randomness and recursive enumerability
• The definition of random sequences

Cited in

(18)

• Random semicomputable reals revisited
• Computing halting probabilities from other halting probabilities
• in number theory
• Constant compression and random weights
• Present random computations in a uniform way
• Computer runtimes and the length of proofs. With an algorithmic probabilistic application to waiting times in automatic theorem proving
• HOW MUCH INFORMATION CAN THERE BE IN A REAL NUMBER?
• A program-size complexity measure for mathematical problems and conjectures
• Chaitin's as a continuous function
• Searching for shortest and least programs
• Nonnormality of Stoneham constants
• Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
• The complexity of the four colour theorem
• scientific article; zbMATH DE number 1543065 (Why is no real title available?)
• Inductive complexity measures for mathematical problems
• Chaitin numbers and halting problems
• scientific article; zbMATH DE number 2066189 (Why is no real title available?)
• Computing with Very Weak Random Sources

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

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