- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: <juergen.domain.name.hidden>

Date: Wed, 6 Dec 2000 09:50:27 +0100

I am pleased to announce a new paper on computable universes, inductive

inference and Occam's razor. It might be of interest to theoretical

computer scientists, mathematicians, physicists, and philosophers. All

comments are welcome, in particular: corrections, suggestions for

improving readability, simplifications of proofs, references / pointers

to be added or replaced or deleted, etc.

ALGORITHMIC THEORIES OF EVERYTHING

Juergen Schmidhuber, IDSIA, Switzerland

We make the plausible assumption that the history of our universe is

formally describable, and sampled from a formally describable probability

distribution on the possibly infinite histories. To study consequences

for observers evolving within such a universe, we generalize the concepts

of decidability, halting problem, Kolmogorov's algorithmic complexity,

and Solomonoff's algorithmic probability. We describe objects "more

random" than Chaitin's halting probability of a Turing machine, show

that there is a universal cumulatively enumerable measure (CEM) that

dominates previous measures for inductive inference, prove that any CEM

must assign low probabilities to universes without short enumerating

programs, that any describable measure must assign low probabilities

to universes without short descriptions, and several similar "Occam's

razor theorems." Then we discuss the most efficient way of computing all

universes based on Levin's optimal search algorithm, and make a natural

resource-oriented postulate: the cumulative prior probability of all

objects incomputable within time t by this optimal algorithm should

be inversely proportional to t. We derive consequences for inductive

inference, physics, and philosophy, predicting that whatever seems random

is not, but in fact is computed by a short and fast algorithm which will

probably halt before our universe is many times older than it is now.

Date: Wed, 6 Dec 2000 09:50:27 +0100

I am pleased to announce a new paper on computable universes, inductive

inference and Occam's razor. It might be of interest to theoretical

computer scientists, mathematicians, physicists, and philosophers. All

comments are welcome, in particular: corrections, suggestions for

improving readability, simplifications of proofs, references / pointers

to be added or replaced or deleted, etc.

ALGORITHMIC THEORIES OF EVERYTHING

Juergen Schmidhuber, IDSIA, Switzerland

We make the plausible assumption that the history of our universe is

formally describable, and sampled from a formally describable probability

distribution on the possibly infinite histories. To study consequences

for observers evolving within such a universe, we generalize the concepts

of decidability, halting problem, Kolmogorov's algorithmic complexity,

and Solomonoff's algorithmic probability. We describe objects "more

random" than Chaitin's halting probability of a Turing machine, show

that there is a universal cumulatively enumerable measure (CEM) that

dominates previous measures for inductive inference, prove that any CEM

must assign low probabilities to universes without short enumerating

programs, that any describable measure must assign low probabilities

to universes without short descriptions, and several similar "Occam's

razor theorems." Then we discuss the most efficient way of computing all

universes based on Levin's optimal search algorithm, and make a natural

resource-oriented postulate: the cumulative prior probability of all

objects incomputable within time t by this optimal algorithm should

be inversely proportional to t. We derive consequences for inductive

inference, physics, and philosophy, predicting that whatever seems random

is not, but in fact is computed by a short and fast algorithm which will

probably halt before our universe is many times older than it is now.

--- The essential results of the paper should be of interest from a purely theoretical point of view independent of the motivation through formally describable universes. To get to the meat of the report you may want to skip Section 1; the main results are in Sections 3, 4, 5, 6.2, 6.5. Here is a condensed outline of the technical contents. Section 2 introduces general Turing Machines (GTMs) that can edit their previous outputs, and enumerable output machines (EOMs) that can do this provided the output does not decrease lexicographically. We define: a formally describable bitstring x has a finite, never halting program that computes x such that each output bit is modified at most finitely many times, that is, each finite beginning of x eventually converges and ceases to change (Def 2.1-2.5, p 9). Section 3 generalizes the Kolmogorov complexity of x to the case of (possibly infinite) x describable on EOMs and GTMs. It is shown (Theorem 3.3, p 15) that there are x with short GTM descriptions yet incompressible on EOMs and therefore "more random" than Chaitin's Omega, which is incompressible only on traditional, monotone TMs. This yields a natural TM type-specific complexity hierarchy (p 16). Using the results above, Section 4 extends previous work on enumerable semimeasures by Solomonoff and Levin and others. It introduces cumulatively enumerable measures (CEMs, Def. 4.4, p 17), where the cumulative probability of all y lexicographically greater than x is enumerable. It is shown that there is a universal CEM that dominates all other CEMs as well as previous enumerable measures, in the sense that it assigns higher probability to any finite y, save for a constant factor independent of y (Theorem 4.1, p 18). This probability is shown to be equivalent to the probability that an EOM whose input bits are chosen randomly produces an output starting with y (Corollary 4.3 and Lemma 4.2., p 24). Section 4 also features Hutter's proof that there is no universal approximable measure (Theorem 4.2, p 20). Section 5 establishes relations between generalized Kolmogorov complexity and algorithmic probability. It is shown that the universal CEM assigns a probability to each enumerable x proportional to 1/2 raised to the power of the length of x's minimal EOM-based description, times a small correction factor (Theorem 5.3, p. 26), and that objects with approximable probabilities yet without very short descriptions on GTMs are necessarily very unlikely (Theorem 5.5, p 28). Additional suspected links between generalized K-complexity and probability are expressed in form of conjectures 5.1, 5.2, 5.3 (p 29). Section 6.2 introduces the "S-describable" universes computable within countable time, and the fastest way of computing all of them (p 31), based on Levin's universal search algorithm. Somewhat surprisingly, this algorithm essentially computes each computable universe as quickly as its fastest program, without being slowed down much by the simultaneous computation of all the other universes. Section 6.5 then derives a natural resource-oriented prior bias: the collective probability of all objects incomputable in phase i of the optimal algorithm is discounted by 2^-i (Def 6.3, p 34). Given the resulting "speed prior," Theorem 6.1 and Corollary 6.1 show that the best way of predicting a future y from past observations x is to minimize the Levin complexity of (x,y). Section 7 analyzes the inference problem of observers evolving in universes sampled from the novel algorithmic priors above, makes appropriate predictions for our own universe, and discusses their falsifiability. --- Version 1.0, 30 Nov 2000; 55 pages, 10 theorems, 71 references ftp://ftp.idsia.ch/pub/juergen/toes.ps.gz (gzipped postscript, 146K) ftp://ftp.idsia.ch/pub/juergen/toes.ps (postscript, 481K) ftp://ftp.idsia.ch/pub/juergen/toes.tex (latex, 142K) ftp://ftp.idsia.ch/pub/juergen/toes.tex.gz (gzipped latex, 47K) http://www.idsia.ch/~juergen/onlinepub.html (various formats) http://arXiv.org/abs/quant-ph/0011122 (various formats)Received on Wed Dec 06 2000 - 00:52:21 PST

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:07 PST
*