At the age of 17 my brother Christof declared that the universe is
a mathematical structure inhabited by observers who are mathematical
substructures (private communication, Munich, 1981). As he went on to
become a theoretical physicist, discussions with him about the relation
between superstrings and bitstrings became a source of inspiration
for writing both the earlier paper [#!Schmidhuber:97brauer!#] and the
present one, both based on computational complexity theory, which seems
to provide the natural setting for his more physics-oriented ideas
(private communication, Munich 1981-86; Pasadena 1987-93; Princeton
1994-96; Berne/Geneva 1997-; compare his notion of *``mathscape''*
[#!Christof:00!#]). Furthermore, Christof's 1997 remarks on similarities
and differences between Feynman path integrals and ``the sum of all
computable universes'' and his resulting dissatisfaction with the lack of
a discussion of temporal aspects in [#!Schmidhuber:97brauer!#] triggered
Section 6 on temporal complexity.

I am grateful to Ray Solomonoff for his helpful comments on earlier
work [#!Schmidhuber:97nn!#] making use of the probabilistic algorithm
of Section 6, and to Paul Vitányi for useful
information relevant to the proof of Theorem 4.2. I would
also like to express my thanks to numerous posters and authors (e.g.,
[#!Marchal:98!#,#!Tegmark:98!#,#!Moravec:99!#,#!Bostrom:00!#,#!Standish:00!#,#!Donald:90!#,#!Higgo:99!#,#!Mallah:00!#,#!Ruhl:00!#])
of the *everything mailing list* created by Wei Dai [#!Dai:98!#]
*(everything-list@eskimo.com)*. Some of the text above actually
derives from my replies to certain postings (see archive at *
http://www.escribe.com/science/theory/*).
Finally I am indebted
to Marcus Hutter and Sepp Hochreiter for independently checking the theorems,
to Leonora Bianchi,
Wei Dai,
Doug Eck,
Felix Gers,
Ivo Kwee,
Carlo Lepori,
Leonid Levin,
Monaldo Mastrolilli,
Andrea Rizzoli,
Nicol N. Schraudolph,
and Marco Zaffalon,
for comments on (parts of) earlier drafts
or of Version 1.0 [#!Schmidhuber:00version1!#],
to Wilfried Brauer and Karl Svozil for relevant pointers and references,
and especially to Marcus Hutter for the proof of Theorem 4.2.

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