Jim, There is a simple proof of convergence for the sum involved in defining the probability of a given string in the Solomonoff distribution:
At its greatest, a particular string would be output by *all* programs. In this case, its sum would come to 1. This puts an upper bound on the sum. Since there is no subtraction, there is a lower bound at 0 and the sum monotonically increases as we take the limit. Knowing these facts, suppose it *didn't* converge. It must then increase without bound, since it cannot fluctuate back and forth (it can only go up). But this contradicts the upper bound of 1. So, the sum must stop at 1 or below (and in fact we can prove it stops below 1, though we can't say where precisely without the infinite computing power required to compute the limit). --Abram On Wed, Jul 14, 2010 at 11:29 AM, Jim Bromer <jimbro...@gmail.com> wrote: > Last week I came up with a sketch that I felt showed that Solomonoff > Induction was incomputable *in practice* using a variation of Cantor's > Diagonal Argument. I wondered if my argument made sense or not. I will > explain why I think it did. > > > > First of all, I should have started out by saying something like, Suppose > Solomonoff Induction was computable, since there is some reason why people > feel that it isn't. > > > > Secondly I don't think I needed to use Cantor's Diagonal Argument (for the > *in practice* case), because it would be sufficient to point out that > since it was impossible to say whether or not the probabilities ever > approached any sustained (collared) limits due to the lack of adequate > mathematical definition of the concept "all programs", it would be > impossible to make the claim that they were actual representations of the > probabilities of all programs that could produce certain strings. > > > > But before I start to explain why I think my variation of the Diagonal > Argument was valid, I would like to make another comment about what was > being claimed. > > > > Take a look at the n-ary expansion of the square root of 2 (such as the > decimal expansion or the binary expansion). The decimal expansion or the > binary expansion of the square root of 2 is an infinite string. To say > that the algorithm that produces the value is "predicting" the value is a > torturous use of meaning of the word 'prediction'. Now I have less than > perfect grammar, but the idea of prediction is so important in the field of > intelligence that I do not feel that this kind of reduction of the concept > of prediction is illuminating. > > > > Incidentally, There are infinite ways to produce the square root of 2 (sqrt > 2 +1-1, sqrt2 +2-2, sqrt2 +3-3,...). So the idea that the square root of > 2 is unlikely is another stretch of conventional thinking. But since > there are an infinite ways for a program to produce any number (that can be > produced by a program) we would imagine that the probability that one of the > infinite ways to produce the square root of 2 approaches 0 but never reaches > it. We can imagine it, but we cannot prove that this occurs in Solomonoff > Induction because Solomonoff Induction is not limited to just this class of > programs (which could be proven to approach a limit). For example, we > could make a similar argument for any number, including a 0 or a 1 which > would mean that the infinite string of digits for the square root of 2 is > just as likely as the string "0". > > > > But the reason why I think a variation of the diagonal argument can work in > my argument is that since we cannot prove that the infinite computations of > the probabilities that a -program will produce a string- will ever approach > a limit, to use the probabilities reliably (even as an infinite theoretical > method) we would have to find some way to rearrange the computations of the > probabilities so that they could. While the number of ways to rearrange > the ordering of a finite number of things is finite no matter how large the > number is, the number of possible ways to rearrange an infinite number of > things is infinite. I believe that this problem of finding the right > rearrangement of an infinite list of computations of values after the > calculation of the list is finished qualifies for an infinite to infinite > diagonal argument. > > > I want to add one more thing to this in a few days. > > Jim Bromer > *agi* | Archives <https://www.listbox.com/member/archive/303/=now> > <https://www.listbox.com/member/archive/rss/303/> | > Modify<https://www.listbox.com/member/?&;>Your Subscription > <http://www.listbox.com> > -- Abram Demski http://lo-tho.blogspot.com/ http://groups.google.com/group/one-logic ------------------------------------------- agi Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: https://www.listbox.com/member/?member_id=8660244&id_secret=8660244-6e7fb59c Powered by Listbox: http://www.listbox.com
