Abram, We all have some misconceptions about this, and about related issues. Let me think about this more carefully and I will answer during the next week - or two, (I have already reached my quota of egregious errors in this thread). Jim
On Mon, Jul 26, 2010 at 2:54 PM, Abram Demski <[email protected]> wrote: > Jim, > > I'll argue that solomonoff probabilities are in fact like Pi, that is, > computable in the limit. > > I still do not understand why you think these combinations are necessary. > It is not necessary to make some sort of ordering of the sum to get it to > converge: ordering only matters for infinite sums which include negative > numbers. (Perhaps that's where you're getting the idea?) > > Here's my proof, rewritten from an earlier post, using the properties of > infinite sums of non-negative numbers. > > (preliminaries) > > Define the computation as follows: we start with a string S which we want > to know the Solomonoff probability of. We are given a time-limit T. We start > with P=0, where P is a real number with precision 2*log_4(T) or more. We use > some binary encoding for programs which (unlike normal programming > languages) does not contain syntactically invalid programs, but still will > (of course) contain infinite loops and so on. We run program "0" and "1" for > T/4 each, "00", "01", "10" and "11" for T/16 each, and in general run each > program of length N for floor[T/(4^N)] until T/(4^N) is less than 1. Each > time we run a program and the result is S, we add 1/(4^N) to P. > > (assertion) > > P converges to some value as T is increased. > > (proof) > > If every single program were to output S, then T would converge to 1/4 + > 1/4 + 1/16 + 1/16 + 1/16 + 1/16 + ... that is, 2*(1/(4^1)) + 4*(1/(4^2)) + > 8*(1/(4^3)) + ... which comes to 1/2 + 1/4 + 1/8 + 1/16 + .. i.e. 1/(2^1) + > 1/(2^2) + 1/(2^3) + ... ; it is well-known that this sequence converges to > 1. Thus 1 is an upper bound for P: it could only get that high if every > single program were to output S. > > 0 is a lower bound, since we start there and never subtract anything. In > fact, every time we add more to P, we have a new lower bound: P will never > go below a number once it reaches it. The sum can only increase. Infinite > sums with this property must either converge to a finite number, or go to > infinity. However, we already know that 1 is an upper bound for P; so, it > cannot go to infinity. Hence, it must converge. > > --Abram > > On Mon, Jul 26, 2010 at 9:14 AM, Jim Bromer <[email protected]> wrote: > >> As far as I can tell right now, my theories that Solomonoff Induction >> is trans-infinite were wrong. Now that I realize that the mathematics do >> not support these conjectures, I have to acknowledge that I would not be >> able to prove or even offer a sketch of a proof of my theories. Although I >> did not use rigourous mathematics while I have tried to make an assessment >> of the Solomonoff method, the first principle of rigourous mathematics is to >> acknowledge that the mathematics does not support your supposition when they >> don't. >> >> Solomonoff Induction isn't a mathematical theory because the desired >> results are not computable. As I mentioned before, there are a great many >> functions that are not computable but which are useful and important because >> they tend toward a limit which can be seen in with a reasonable number of >> calculations using the methods available. Pi is one such function. (I am >> presuming that pi would require an infinite expansion which seems right.) >> >> I have explained, and I think it is a correct explanation, that there is >> no way that you could make an apriori computation of all possible >> combinations taken from infinite values. So you could not even come up with >> a theoretical construct that could take account of that level of >> complexity. It is true that you could come up with a theoretical >> computational method that could take account of any finite number of values, >> and that is what we are talking about when we talk about the infinite, but >> in this context it only points to a theoretical paradox. Your theoretical >> solution could not take the final step of computing a probability for a >> string until it had run through the infinite combinations and this is >> impossible. The same problem does not occur for pi because the function >> that produces it tends toward a limit. >> >> The reason I thought Solomonoff Induction was trans-infinite was because I >> thought it used the Bayesian notion to compute the probability using all >> possible programs that produced a particular substring following a given >> prefix. Now I understand that the desired function is the computation of >> only the probability of a particular string (not all possible substrings >> that are identical to the string) following a given prefix. I want to study >> the method a little further during the next few weeks, but I just wanted to >> make it clear that, as far as now understand the program, that I do not >> think that it is trans-infinite. >> >> 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> > <https://www.listbox.com/member/archive/rss/303/> | > Modify<https://www.listbox.com/member/?&;>Your Subscription > <http://www.listbox.com/> > ------------------------------------------- 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
