endoself comments on Risks of downloading alien AI via SETI search - Less Wrong

9 Post author: turchin 15 March 2013 10:25AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (98)

You are viewing a single comment's thread. Show more comments above.

Comment author: endoself 15 March 2013 09:50:28PM *  2 points [-]

Say your bit string is s and the program you find that outputs s is p. Now you know that K(s) ≤ |p|, meaning the length of p. However, we wanted to show that K(s)>L, so the bound is in the wrong direction. We need to show that there's no shorter program that also outputs s, which is impossible by Chaitin's theorem.

The actual proof of Chaitin's theorem is somewhat similar to your argument here. Basically, if we have can prove that any string has a Kolmogorov complexity greater than L, we write a program to search through all proofs until it find a proof that some string s has complexity greater than L and outputs that string. By choosing L sufficiently large, this program itself has complexity less than L, but it outputs s, contradicting K(s)>L.