Confused about Solomonoff induction
post by nebulous · 2012-07-13T11:36:12.375Z · LW · GW · Legacy · 9 commentsWhy wouldn't the probability of two algorithms of different lengths appearing approach the same value as longer strings of bits are searched?
9 comments
Comments sorted by top scores.
comment by Oscar_Cunningham · 2012-07-13T11:43:59.038Z · LW(p) · GW(p)
Better suited to the open thread.
Replies from: nebulouscomment by private_messaging · 2012-07-13T19:22:15.362Z · LW(p) · GW(p)
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.
Replies from: nebulouscomment by Manfred · 2012-07-13T13:49:29.756Z · LW(p) · GW(p)
Because when you integrate an exponential, you get a constant.
Replies from: prase↑ comment by prase · 2012-07-13T19:47:07.365Z · LW(p) · GW(p)
Is this a joke?
Replies from: Manfred↑ comment by Manfred · 2012-07-14T02:55:34.269Z · LW(p) · GW(p)
Ah, I misunderstood the question. I thought he thought that the solomonoff prior wouldn't be normalized - so for example, a program of length 30 and a program of length 33 would both be in infinite strings, so as you search infinity strings you find them equally common.
Replies from: prase↑ comment by prase · 2012-07-14T10:46:14.764Z · LW(p) · GW(p)
Still I don't understand the "exponential" part. I thought that you may have deliberately given an obscure brief answer to the obscure brief question in the OP.
Replies from: Manfred↑ comment by Manfred · 2012-07-14T12:08:57.160Z · LW(p) · GW(p)
So what happens is that as you search more and more strings, they get weighted exponentially (i.e. like e^-length), so even though the program of length 30 and the program of length 33 show up in infinite strings, when you sum up the total weight, you get two different constants.