No, I might have been wrong about the feasibility of writing an algorithm that can produce all the possible combinations of items when I wrote my last message. It is because the word "combination" is associated with more than one mathematical method. I am skeptical of the possibility that there is a re algorithm that can write out every possible combination of items taken from more than one group of *types* when strings of infinite length are possible.
So yes, I may have proved that there is no re algorithm, even if given infinite resources, that can order the computation of Solomonoff Induction in such a way to show that the probability (or probabilities) tend toward a limit. If my theory is correct, and right now I would say that there is a real chance that it is, I have proved that Solmonoff Induction is theoretically infeasible, illogical and therefore refuted. Jim Bromer On Sun, Jul 25, 2010 at 9:02 AM, Jim Bromer <jimbro...@gmail.com> wrote: > 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
