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 t0 such that for all
:
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.