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
-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 , and the enumerable ``number of wisdom'' [#!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.

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.

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
of *x* in the following sense.
There exists a possibly never halting computer which outputs a sequence of numbers
at discrete times
in response to input
such that for each real
there exists a finite
time *t*_{0} such that for all
:

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 2^{n} 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.

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