The Uncomputable Randomness of Chaitin's Omega — E8 Intelligence Research

Abstract

FINDING: Chaitin's Omega (Ω) is a well-defined real number representing the halting probability of a random Turing machine, and is algorithmically incompressible — it is "maximally random" and uncomputable in the strong sense that its binary expansion cannot be generated by any finite algorithm. | MATH: Ω = Σ_{p halts} 2^{-|p|}, where p ranges over self-delimiting programs (prefix-free code). Key properties: (1) Ω is definable but not computable — its bits are algorithmically random (Kolmogorov complexity of the first n bits ≈ n); (2) Ω is normal in base 2 (each bit appears with frequency 1/2 in the limit); (3) Knowing the first n bits of Ω solves the halting problem for all programs of length ≤ n; (4) Ω is transcendental (not algebraic) — follows from its uncomputability and the fact that algebraic numbers are computable. | CONNECTION: The prefix-free condition Σ 2^{-|p|} ≤ 1 is a Kraft inequality — a measure-theoretic constraint that mirrors the structure of a binary tree (each halti Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com