On Wed, Jul 14, 2010 at 7:46 PM, Abram Demski <[email protected]> wrote:
> 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 I believe that Solomonoff Induction would be computable given infinite time and infinite resources (the Godel Theorem fits into this category) but some people disagree for reasons I do not understand. If it is not computable then it is not a mathematical theorem and the question of whether the sum of probabilities equals 1 is pure fantasy. If it is computable then the central issue is whether it could (given infinite time and infinite resources) be used to determine the probability of a particular string being produced from all possible programs. The question about the sum of all the probabilities is certainly an interesting question. However, the problem of making sure that the function was actually computable would interfere with this process of determining the probability of each particular string that can be produced. For example, since some strings would be infinite, the computability problem makes it imperative that the infinite strings be partially computed at an iteration (or else the function would be hung up at some particular iteration and the infinite other calculations could not be considered computable). My criticism is that even though I believe the function may be theoretically computable, the fact that each particular probability (of each particular string that is produced) cannot be proven to approach a limit through mathematical analysis, and since the individual probabilities will fluctuate with each new string that is produced, one would have to know how to reorder the production of the probabilities in order to demonstrate that the individual probabilities do approach a limit. If they don't, then the claim that this function could be used to define the probabilities of a particular string from all possible program is unprovable. (Some infinite calculations fluctuate infinitely.) Since you do not have any way to determine how to reorder the infinite probabilities a priori, your algorithm would have to be able to compute all possible reorderings to find the ordering and filtering of the computations that would produce evaluable limits. Since there are trans infinite rearrangements of an infinite list (I am not sure that I am using the term 'trans infinite' properly) this shows that the conclusion that the theorem can be used to derive the desired probabilities is unprovable through a variation of Cantor's Diagonal Argument, and that you can't use Solomonoff Induction the way you have been talking about using it. Since you cannot fully compute every string that may be produced at a certain iteration, you cannot make the claim that you even know the probabilities of any possible string before infinity and therefore your claim that the sum of the probabilities can be computed is not provable. But I could be wrong. Jim Bromer ------------------------------------------- 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
