Introduction to Describable Universes next up previous contents
Next: Outline of Main Results Up: No Title Previous: Contents

Introduction to Describable Universes

An object X is formally describable if a finite amount of information completely describes X and only X. More to the point, X should be representable by a possibly infinite bitstring x such that there is a finite, possibly never halting program p that computes x and nothing but x in a way that modifies each output bit at most finitely many times; that is, each finite beginning of x eventually converges and ceases to change. Definitions 2.1-2.5 will make this precise, and Sections 2-3 will clarify that this constructive notion of formal describability is less restrictive than the traditional notion of computability [#!Turing:36!#], mainly because we do not insist on the existence of a halting program that computes an upper bound of the convergence time of p's n-th output bit. Formal describability thus pushes constructivism [#!Brouwer:07!#,#!Beeson:85!#] to the extreme, barely avoiding the nonconstructivism embodied by even less restrictive concepts of describability (compare computability in the limit [#!Gold:65!#,#!Putnam:65!#,#!Freyvald:74!#] and $\Delta^0_n$-describability [#!Rogers:67!#][#!LiVitanyi:97!#, p. 46-47]). The results in Sections 2-5 will exploit the additional degrees of freedom gained over traditional computability, while Section 6 will focus on another extreme, namely, the fastest way of computing all computable objects.

Among the formally describable things are the contents of all books ever written, all proofs of all theorems, the infinite decimal expansion of $\sqrt{17}$, and the enumerable ``number of wisdom'' $\Omega$ [#!Chaitin:87!#,#!Slaman:99!#,#!Calude:00!#,#!Solovay:00!#]. Most real numbers, however, are not individually describable, because there are only countably many finite descriptions, yet uncountably many reals, as observed by Cantor in 1873 [#!Cantor:1874!#]. It is easy though to write a never halting program that computes all finite prefixes of all real numbers. In this sense certain sets seem describable while most of their elements are not.

What about our universe, or more precisely, its entire past and future history? Is it individually describable by a finite sequence of bits, just like a movie stored on a compact disc, or a never ending evolution of a virtual reality determined by a finite algorithm? If so, then it is very special in a certain sense, just like the comparatively few describable reals are special.

Example 1.1 (Pseudorandom universe)   Let x be an infinite sequence of finite bitstrings $x^1,x^2,\ldots$ representing the history of some discrete universe, where xk represents the state of the universe at discrete time step k, and x1 the ``Big Bang'' (compare [#!Schmidhuber:97brauer!#]). Suppose there is a finite algorithm A that computes xk+1 ($k \geq 1$) from xk and additional information noisek (this may require numerous computational steps of A, that is, ``local'' time of the universe may run comparatively slowly). Assume that noisek is not truly random but calculated by invoking a finite pseudorandom generator subroutine [#!Allender:89!#]. Then x is describable because it has a finite constructive description.

Contrary to a widely spread misunderstanding, quantum physics, quantum computation (e.g., [#!Bennett:00!#,#!Deutsch:97!#,#!Penrose:89!#]) and Heisenberg's uncertainty principle do not rule out that our own universe's history is of the type exemplified above. It might be computable by a discrete process approximated by Schrödinger's continuous wave function, where noisek determines the ``collapses'' of the wave function. Since we prefer simple, formally describable explanations over complex, nondescribable ones, we assume the history of our universe has a finite description indeed.

This assumption has dramatic consequences. For instance, because we know that our future lies among the few (countably many) describable futures, we can ignore uncountably many nondescribable ones. Can we also make more specific predictions? Does it make sense to say some describable futures are necessarily more likely than others? To answer such questions we will examine possible probability distributions on possible futures, assuming that not only the histories themselves but also their probabilities are formally describable. Since most (uncountably many) real-valued probabilities are not, this assumption -- against which there is no physical evidence -- actually represents a major inductive bias, which turns out to be strong enough to explain certain hitherto unexplained aspects of our world.

Example 1.2 (In which universe am I?)   Let h(y) represent a property of any possibly infinite bitstring y, say, h(y)=1 if y represents the history of a universe inhabited by a particular observer (say, yourself) and h(y)=0 otherwise. According to the weak anthropic principle [#!Carter:74!#,#!BarrowTipler:86!#], the conditional probability of finding yourself in a universe compatible with your existence equals 1. But there may be many y's satisfying h(y)=1. What is the probability that y=x, where x is a particular universe satisfying h(x)=1? According to Bayes,

 \begin{displaymath}P(x=y \mid h(y)=1)
= \frac{P(h(y)=1 \mid x=y) P(x = y)} {\sum_{z:h(z)=1} P(z)}
\propto P(x)
\end{displaymath} (1)

where $P(A \mid B)$ denotes the probability of A, given knowledge of B, and the denominator is just a normalizing constant. So the probability of finding yourself in universe x is essentially determined by P(x), the prior probability of x.

Each prior P stands for a particular ``theory of everything'' or TOE. Once we know something about P we can start making informed predictions. Parts of this paper deal with the question: what are plausible properties of P? One very plausible assumption is that P is approximable for all finite prefixes $\bar{x}$ of x in the following sense. There exists a possibly never halting computer which outputs a sequence of numbers $T(t,\bar{x})$ at discrete times $t=1,2,\ldots$ in response to input $\bar{x}$ such that for each real $\epsilon > 0$ there exists a finite time t0 such that for all $t \geq t_0$:

 \begin{displaymath}\mid P(\bar{x}) - T(t,\bar{x}) \mid < \epsilon .
\end{displaymath} (2)

Approximability in this sense is essentially equivalent to formal describability (Lemma 2.1 will make this more precise). We will show (Section 5) that the mild assumption above adds enormous predictive power to the weak anthropic principle: it makes universes describable by short algorithms immensely more likely than others. Any particular universe evolution is highly unlikely if it is determined not only by simple physical laws but also by additional truly random or noisy events. To a certain extent, this will justify ``Occam's razor'' (e.g., [#!Blumer:87!#]) which expresses the ancient preference of simple solutions over complex ones, and which is widely accepted not only in physics and other inductive sciences, but even in the fine arts [#!Schmidhuber:97art!#].

All of this will require an extension of earlier work on Solomonoff's algorithmic probability, universal priors, Kolmogorov complexity (or algorithmic information), and their refinements [#!Kolmogorov:65!#,#!Solomonoff:64!#,#!Chaitin:69!#,#!Zvonkin:70!#,#!Levin:73a!#,#!Levin:74!#,#!Gacs:74!#,#!Chaitin:75!#,#!Gacs:83!#,#!Schnorr:73!#,#!Solomonoff:78!#,#!Chaitin:87!#,#!Barzdin:88!#,#!Cover:89!#,#!Uspensky:92!#,#!LiVitanyi:97!#]. We will prove several theorems concerning approximable and enumerable objects and probabilities (Sections 2-5; see outline below). These theorems shed light on the structure of all formally describable objects and extend traditional computability theory; hence they should also be of interest without motivation through describable universes.

The calculation of the subjects of these theorems, however, may occasionally require excessive time, itself often not even computable in the classic sense. This will eventually motivate a shift of focus on the temporal complexity of ``computing everything'' (Section 6). If you were to sit down and write a program that computes all possible universes, which would be the best way of doing so? Somewhat surprisingly, a modification of Levin Search [#!Levin:73!#] can simultaneously compute all computable universes in an interleaving fashion that outputs each individual universe as quickly as its fastest algorithm running just by itself, save for a constant factor independent of the universe's size. This suggests a more restricted TOE that singles out those infinite universes computable with countable time and space resources, and a natural resource-based prior measure S on them. Given this ``speed prior'' S, we will show that the most likely continuation of a given observed history is computable by a fast and short algorithm (Section 6.6).

The S-based TOE will provoke quite specific prophecies concerning our own universe (Section 7.5). For instance, the probability that it will last 2n times longer than it has lasted so far is at most 2-n. Furthermore, all apparently random events, such as beta decay or collapses of Schrödinger's wave function of the universe, actually must exhibit yet unknown, possibly nonlocal, regular patterns reflecting subroutines (e.g., pseudorandom generators) of our universe's algorithm that are not only short but also fast.

next up previous contents
Next: Outline of Main Results Up: No Title Previous: Contents
Juergen Schmidhuber

Related links: In the beginning was the code! - Zuse's thesis - Life, the universe, and everything - Generalized Algorithmic Information - Speed Prior - The New AI