See 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). 2 Basing it on combinatory
logic See the prefix coding system described in Binary Lambda
Calculus and Combinatory Logic (page 20) written by John Tromp:
of course, c, d are meta-variables, and also some other
notations are changed slightly. Having seen this, decoding is
rather straightforward. Let us represent it e.g with the
following LL1 parser. Of course, we can build it on top of more
sophisticated parser libraries (Parsec, arrow parsers) 2.2.1
Decoding module module Decode (clP) where import Parser (Parser,
item) import CL (CL, k, s, apply) import CLExt ((>>^)) clP ::
Parser Bool CL clP = item (bool applicationP baseP) applicationP
:: Parser Bool CL applicationP = clP >>^ clP baseP :: Parser
Bool CL baseP = item (bool k s) kP, sP :: Parser Bool CL kP =
return k sP = return s 2.2.2 Com