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 | Modify Your Subscription ------------------------------------------- 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
