Monday, July 16, 2007

Proof Of Chaitin Incompleteness as Non-Computability of Kolmogorov Complexity.

This is the first of several postiings leading up to a epistomological arguments on Intelligent Design and Richard Dawkins' God Delusion . This is a loose, but formal demonstration of Chaitin's proof of the elusiveness of a "Designer that is more elegant than what is Designed."

I will follow this (soon) with a simple derivation from Berry's Paradox (which inspired Chaitin).

(i) A String O may be regarded as the output of a possible infinite number of programs {P}.
(ii) Define ‘X’ meaning a program X that outputs Y.
(iii) Each program of {P} has a measurable length in bits. So, if Pw Î {P} then Pw is the length in bits.
(iv) The “Kolmogorov Complexity” of a String O is defined as:
K(O): Pk Î {P} É Pk <= O + c where c is a maximum. Thus Pk is a minimal (or 'elegant' in Chaitin's terminology) program producing O as output.


Aq: Given a sufficiently large n, there is no program, procedure, or proof-string that can represent “K(s) ≥ n” where s is an arbitrary string. IOW: Given a threshold n, one cannot compute K(s) for some s and yields a complexity ≥ n.

Proof by Contradiction:

Bq : ~Aq

Therefore, there exists a program Pp(n), s.t. given a number ‘n’ Pp(n) outputs a string O where K(O) >= n.

In defining Pp(n), we perform the following.
(1) Aggregate all programs {P} in a certain order: by size and lex.
(2) Test each program m of length q with function TE(Pm where Pm = q).
(3) If q = K(O) and if q >= n, return O, otherwise return nothing.
(4) We see that Pp(n) = Pp + log2n bits. Call this sum n1.
(5) Choose a new n0, where n0 > n1 where log2n0 = log2n1. (I.e. numbers have same # bits to represent themselves, but where the actual numeric n0 > numeric n1).
(6) Pp(n0) is undecidable. The program Pp(n0) is actually smaller in size than n0. Yet, O is the output of a minimal-complex-program Pm whose size is > n0. But the program Pp(n) has outputted O.
(7) Thus the program Pm is not a minimal-complex-program outputting O since it is larger than Pp(n).
(8) Therefore, Bq is false, and Aq is true by excluded middle. QED