### 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'

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.

Theorem:

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 programPp(n), s.t. given a number ‘n’ Pp(n) outputs a string O where K(O) >= n.

In definingPp(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 thatPp(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 thanPp(n).

(8) Therefore, Bq is false, and Aq is true by excluded middle. QED

*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 ‘

(iii) Each program of {

(iv) The “Kolmogorov Complexity” of a String O is defined as:

K(O):

Theorem:

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

In defining

(1) Aggregate all programs {P} in a certain order: by size and lex.

(2) Test each program m of length q with function TE(

(3) If q = K(O) and if q >= n, return O, otherwise return nothing.

(4) We see that

(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).

(7) Thus the program Pm is not a minimal-complex-program outputting O since it is larger than

(8) Therefore, Bq is false, and Aq is true by excluded middle. QED

## 0 Comments:

Post a Comment

<< Home