next up previous
Next: Regular and Irregular Universes Up: In C. Freksa, ed., Previous: In C. Freksa, ed.,

Preliminaries

Assumptions. A long time ago, the Great Programmer wrote a program that runs all possible universes on His Big Computer. ``Possible'' means ``computable'': (1) Each universe evolves on a discrete time scale. (2) Any universe's state at a given time is describable by a finite number of bits. One of the many universes is ours, despite some who evolved in it and claim it is incomputable.

Computable universes. Let TM denote an arbitrary universal Turing machine with unidirectional output tape. TM's input and output symbols are ``0'', ``1'', and ``,'' (comma). TM's possible input programs can be ordered alphabetically: ``'' (empty program), ``0'', ``1'', ``,'', ``00'', ``01'', ``0,'', ``10'', ``11'', ``1,'', ``,0'', ``,1'', ``,,'', ``000'', etc. Let Ak denote TM's k-th program in this list. Its output will be a finite or infinite string over the alphabet {``0'',``1'',``,''}. This sequence of bitstrings separated by commas will be interpreted as the evolution Ek of universe Uk. If Ek includes at least one comma, then let Ukl denote the l-th (possibly empty) bitstring before the l-th comma. Ukl represents Uk's state at the l-th time step of Ek (k, l in {1, 2, ..., }). Ek is represented by the sequence Uk1, Uk2,..., where Uk1 corresponds to Uk's big bang. Different algorithms may compute the same universe. Some universes are finite (those whose programs cease producing outputs at some point), others are not. I don't know about ours.

TM not important. The choice of the Turing machine is not important. This is due to the compiler theorem: for each universal Turing machine C there exists a constant prefix $\mu_C$ ``0'',``1'',``,''}*, such that for all possible programs p, C's output in response to program $\mu_C p$ is identical to TM's output in response to p. The prefix $\mu_C$ is the compiler that compiles programs for TM into equivalent programs for C.

Computing all universes. One way of sequentially computing all computable universes is dove-tailing. A1 is run for one instruction every second step, A2 is run for one instruction every second of the remaining steps, and so on. Similar methods exist for computing many universes in parallel. Each time step of each universe that is computable by at least one finite algorithm will eventually be computed.

Time. The Great Programmer does not worry about computation time. Nobody presses Him. Creatures which evolve in any of the universes don't have to worry either. They run on local time and have no idea of how many instructions it takes the Big Computer to compute one of their time steps, or how many instructions it spends on all the other creatures in parallel universes.


next up previous
Next: Regular and Irregular Universes Up: In C. Freksa, ed., Previous: In C. Freksa, ed.,
Juergen Schmidhuber
1999-03-15


Related links: In the beginning was the code! - Zuse's thesis - Algorithmic Theories of Everything - Generalized Algorithmic Information - Speed Prior - The New AI