Chaitin's construction

Introduction

Wikipedia article on Chaitin's construction, referring to e.g.

• Computing a Glimpse of Randomness (written by Cristian S. Calude, Michael J. Dinneen, and Chi-Kou Shu)
• Omega and why math has no TOEs (Gregory Chaitin).

Basing it on combinatory logic

Some more direct relatedness to functional programming: we can base $\Omega$ on combinatory logic (instead of a Turing machine), see the prefix coding system described in Binary Lambda Calculus and Combinatory Logic (page 20) written by John Tromp:

${\widehat {\mathbf {S} }}\equiv 00$

${\widehat {\mathbf {K} }}\equiv 01$

${\widehat {\left(xy\right)}}\equiv 1{\widehat {x}}{\widehat {y}}$

of course, $c$, $d$ are metavariables, and also some other notations are changed slightly.

Now, Chaitin's construction will be here

$\sum _{p\in \mathrm {Rng} _{\mathrm {dc} },\;\mathrm {hnf} \left(\mathrm {dc} \;p\right)}2^{-\left|p\right|}$

where

$\mathrm {hnf}$

should denote an unary predicate “has normal form” (“terminates”)

$\mathrm {dc}$

should mean an operator “decode” (a function from finite bit sequences to combinatory logic terms)

$2\!\;^{*}$

should denote the set of all finite bit sequences

$\mathrm {Rng} _{\mathrm {dc} }$

should denote the range of decoding function, e.g. the syntactically correct bit sequences (semantically, they may either terminate or diverge),

“Absolut value”

should mean the length of a bit sequence (not combinatory logic term evaluation!)

Here, $\mathrm {dc}$ is a partial function (from finite bit sequences). If this is confusing or annoying, then we can choose a more Haskell-like approach, making $\mathrm {dc}$ a total function:

 dc :: [Bit] -> Maybe CL

then, Chaitin's construction will be

$\sum _{p\in 2^{*},\;\mathrm {maybe} \;\downarrow \;\mathrm {hnf} \;\left(\mathrm {dc} \;p\right)}2^{-\left|p\right|}$

where $\downarrow$ should denote false truth value.

Related concepts

• Exact real arithmetic
• Combinatory logic
• Computer science
• Mathematics