I believe that trans-infinite would mean that there is no recursively enumerable algorithm that could 'reach' every possible item in the trans-infinite group.
Since each program in Solomonoff Induction, written for a Universal Turing Machine could be written on a single role of tape, that means that every possible combination of programs could also be written on the tape. They would therefore be recursively enumerable just as they could be enumerated on a one to one basis with aleph null (counting numbers). But, unfortunately for my criticism, there are algorithms that could reach any finite combination of things which means that even though you could not determine the ordering of programs that would be necessary to show that the probabilities of each string approach a limit, it would be possible to write an algorithm that could show trends, given infinite resources. This doesn't mean that the probabilities would approach the limit, it just means that if they did, there would be an infinite algorithm that could make the best determination given the information that the programs had already produced. This would be a necessary step of a theoretical (but still non-constructivist) proof. So I can't prove that Solomonoff Induction is inherently trans-infinite. I am going to take a few weeks to see if I can determine if the idea of Solomonoff Induction makes hypothetical sense to me. Jim Bromer On Sat, Jul 24, 2010 at 6:04 PM, Matt Mahoney <matmaho...@yahoo.com> wrote: > Jim Bromer wrote: > > Solomonoff Induction may require a trans-infinite level of complexity > just to run each program. > > "Trans-infinite" is not a mathematically defined term as far as I can tell. > Maybe you mean larger than infinity, as in the infinite set of real numbers > is larger than the infinite set of natural numbers (which is true). > > But it is not true that Solomonoff induction requires more than aleph-null > operations. (Aleph-null is the size of the set of natural numbers, the > "smallest infinity"). An exact calculation requires that you test aleph-null > programs for aleph-null time steps each. There are aleph-null programs > because each program is a finite length string, and there is a 1 to 1 > correspondence between the set of finite strings and N, the set of natural > numbers. Also, each program requires aleph-null computation in the case that > it runs forever, because each step in the infinite computation can be > numbered 1, 2, 3... > > However, the total amount of computation is still aleph-null because each > step of each program can be described by an ordered pair (m,n) in N^2, > meaning the n'th step of the m'th program, where m and n are natural > numbers. The cardinality of N^2 is the same as the cardinality of N because > there is a 1 to 1 correspondence between the sets. You can order the ordered > pairs as (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), (1,4), (2,3), (3,2), > (4,1), (1,5), etc. See > http://en.wikipedia.org/wiki/Countable_set#More_formal_introduction > > Furthermore you may approximate Solomonoff induction to any desired > precision with finite computation. Simply interleave the execution of all > programs as indicated in the ordering of ordered pairs that I just gave, > where the programs are ordered from shortest to longest. Take the shortest > program found so far that outputs your string, x. It is guaranteed that this > algorithm will approach and eventually find the shortest program that > outputs x given sufficient time, because this program exists and it halts. > > In case you are wondering how Solomonoff induction is not computable, the > problem is that after this algorithm finds the true shortest program that > outputs x, it will keep running forever and you might still be wondering if > a shorter program is forthcoming. In general you won't know. > > > -- Matt Mahoney, matmaho...@yahoo.com > > > ------------------------------ > *From:* Jim Bromer <jimbro...@gmail.com> > *To:* agi <agi@v2.listbox.com> > *Sent:* Sat, July 24, 2010 3:59:18 PM > > *Subject:* Re: [agi] Comments On My Skepticism of Solomonoff Induction > > Solomonoff Induction may require a trans-infinite level of complexity just > to run each program. Suppose each program is iterated through the > enumeration of its instructions. Then, not only do the infinity of > possible programs need to be run, many combinations of the infinite programs > from each simulated Turing Machine also have to be tried. All the > possible combinations of (accepted) programs, one from any two or more of > the (accepted) programs produced by each simulated Turing Machine, have to > be tried. Although these combinations of programs from each of the > simulated Turing Machine may not all be unique, they all have to be tried. > Since each simulated Turing Machine would produce infinite programs, I am > pretty sure that this means that Solmonoff Induction is, *by > definition,*trans-infinite. > Jim Bromer > > > On Thu, Jul 22, 2010 at 2:06 PM, Jim Bromer <jimbro...@gmail.com> wrote: > >> I have to retract my claim that the programs of Solomonoff Induction would >> be trans-infinite. Each of the infinite individual programs could be >> enumerated by their individual instructions so some combination of unique >> individual programs would not correspond to a unique program but to the >> enumerated program that corresponds to the string of their individual >> instructions. So I got that one wrong. >> 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/> > *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
