Why wouldn't the probability of two algorithms of different lengths appearing approach the same value as longer strings of bits are searched?

New to LessWrong?

New Comment
9 comments, sorted by Click to highlight new comments since: Today at 6:43 PM

Augh, right. I'd forgotten that was there.

There is no search for a program inside a huge string of bits. The probability of a program is the probability that random string of bits begins with it, which is 2^-len . The programs are self delimited, i.e. the program could be a string like 011011... , the ... being a string of random bits that aren't read or which we decide not to consider to be a program (e.g. if the program simply sets up copying of input tape onto output tape). There's also no search for data inside the huge string of output, it has to begin with data. The 'search' has to be done if you want to find this probability - you have to try every input string.

I get it now. Thanks!