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!#] (email@example.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.