.
Is the universe being computed?
Algorithms
Special Issue
(2010)
Albert Einstein
.
.

Publications on computable universes since 1996:

[9] J. Schmidhuber. The Fastest Way of Computing All Universes. In H. Zenil, ed., A Computable Universe. World Scientific, 2012. PDF of preprint.

[8] J. Schmidhuber. Alle berechenbaren Universen. (All computable universes.) Spektrum der Wissenschaft (German edition of Scientific American), 2007, Spezial 3/07, p. 75-79, 2007. PDF.

[7] J. Schmidhuber: Randomness in physics (Correspondence, Nature 439 p 392, Jan 2006)

[6] J. Schmidhuber. The Computational Universe. Review of Programming the Universe: A Quantum Computer Scientist Takes on the Cosmos, by Seth Lloyd. American Scientist, July-August 2006. HTML.

[5] J.  Schmidhuber. The New AI: General & Sound & Relevant for Physics (HTML). TR IDSIA-04-03. In B. Goertzel and C. Pennachin, eds.: Artificial General Intelligence, p. 175-198, 2006. PDF. PS. PDF. HTML. ArXiv: cs.AI/0302012.

[4] The Speed Prior: A New Simplicity Measure Yielding Near-Optimal Computable Predictions. In J. Kivinen and R. H. Sloan, editors, Proceedings of the 15th Annual Conference on Computational Learning Theory (COLT 2002), Sydney, Australia, Lecture Notes in Artificial Intelligence, pages 216--228. Springer, 2002. PS. PDF. HTML. Based on section 6 of ref [2] below.

[3] Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit. International Journal of Foundations of Computer Science 13(4):587-612, 2002. PDF. PS. Based on sections 2-5 of ref [2] below.

[2] Algorithmic theories of everything (2000). PDF. HTML. ArXiv: quant-ph/ 0011122. Led to refs [3] and [4] above.

[1] A Computer Scientist's View of Life, the Universe, and Everything. LNCS 201-288, Springer, 1997 (submitted 1996). HTML (1996). PS. PS.GZ. PDF. (Later copy in ArXiv.)
.



Jürgen Schmidhuber's

Computable Universes &
Algorithmic Theory of Everything

Digital Physics: Is our universe just the output of a deterministic computer program?

As a consequence of Moore's law, each decade computers are getting roughly 1000 times faster by cost. Apply Moore's law to the video game business. As the virtual worlds get more convincing many people will spend more time in them. Soon most universes will be virtual, only one (the original) will be real. Then many will be led to suspect the real one is a simulation as well. Some are already suspecting this today.

Then the simplest explanation of our universe is the simplest program that computes it. In 1997 Schmidhuber pointed out [1] that the simplest such program actually computes all possible universes with all types of physical constants and laws, not just ours. His essay also talks about universes simulated within parent universes in nested fashion, and about universal complexity-based measures on possible universes.

Here a few video clips on this from the World Science Festival 2011 in NYC: 1. Short video clip of JS & Ed Fredkin talking about Konrad Zuse, pioneer of digital physics. 2. Short clip of JS talking about the information content of the universe. 3. Short clip of JS talking about all computable universes. From Rebooting the Cosmos - Panel Discussion Video: Is the Universe the Ultimate Computer?

Prior measure problem: if every possible future exists, how can we predict anything?

Unfortunately, knowledge about the program that computes all computable universes is not yet sufficient to make good predictions about the future of our own particular universe. Some of our possible futures obviously are more likely than others. For example, tomorrow the sun will probably shine in the Sahara desert. To predict according to Bayes rule, what we need is a prior probability distribution or measure on the possible futures. Which one is the right one? It is not the uniform one: If all futures were equally likely then our world might as well dissolve right now. But it does not.

Some think the famous anthropic principle (AP) might help us here. But it does neither, as will be seen below.

Zuse
Last
update
March
2013

JS@IDSIA
JS@TUM
Pub
AI
.

Zuse's thesis vs quantum physics? Einstein always claimed that `God does not play dice,' and back in 1969 Zuse (top) published a book about what's known today as Zuse's thesis: The universe is being deterministically computed on some sort of giant but discrete computer - compare PDF of MIT's translation (1970) of Zuse's book (1969). Contrary to common belief, Heisenberg's uncertainty principle is no physical evidence against Zuse's thesis - Nobel laureate 't Hooft agrees. Compare [7].



Schmidhuber's overview links:

1. The old Everything Talk (slides)

2. Zuse hypothesis and Zuse himself.

3. Super Omegas and generalizations of algorithmic information and probability. On the measure problem and the non-plus-ultra of constructively describable universes, plus consequences for predicting the future.

4. Speed Prior. On the measure problem and the fastest way of computing any computable universe, plus optimal predictions of the future.

5. Universal learning algorithms plus consequences for optimal inference of laws of computable universes.

6. What simplicity and physics and beauty and the fine arts have in common - compare the formal theory of creativity.

7. Old version of this page (2000).
.

Zuse's thesis: the universe is being computed Randomness and Kolmogorov complexity Speed Prior A 35 year old kind of science Universal AI Goedel machine Kurt Goedel Turing Leibniz Theory of Beauty Publications
Invited plenary talks etc on computable physics etc:

27/6/2011: Carl v. Linde Academy, Munich

4/6/2011 World Science Festival 2011, New York City. Rebooting the Cosmos. Video of panel discussion: Is the Universe the Ultimate Computer?

12/6/2007: Art Meets Science 2007: Randomness vs simplicity & beauty in physics and the fine arts

24/4/2007: ACAT'07: Advanced Computing and Analysis Techniques in Physics Research, Amsterdam

6/11/2006: Zuse Symposium, Berlin: Is the universe a computer?

27/5/2006: Turing Days, Istanbul: computable universes and generalized Kolmogorov complexity

13/5/2005: Data Ecologies, Linz: Digital Physics


Anthropic Principle does not help

The anthropic principle (AP) essentially just says that the conditional probability of finding oneself in a universe compatible with one's existence will always remain 1. AP by itself does not have any additional predictive power. For example, it does not predict that tomorrow the sun will shine in the Sahara, or that gravity will work in quite the same way - neither rain in the Sahara nor certain changes of gravity would destroy us, and thus would be allowed by AP. To make nontrivial predictions about the future we need more than AP - see below!

Predictions for universes sampled from any computable probability distribution

To make better predictions, can we postulate any reasonable nontrivial constraints on the prior probability distribution on our possible futures? Yes! The distribution should at least be computable in the limit. That is, there should exist a program that takes as an input any beginning of the universe history as well as a next possible event, and produces an output converging on the conditional probability of the event. If there were no such program we could not even formally specify our universe, leave alone writing reasonable scientific papers about it.


It turns out that the very weak assumption of a limit-computable probability distribution is enough to make quite nontrivial predictions about our own future. This is the topic of Schmidhuber's work (2000) on Algorithmic Theories of Everything [2]. Sections 2-5 led to generalizations of Kolmogorov's and Solomonoff's complexity and probability measures [3,4].

SPIEGEL cover 30/2002
There is a fastest
way
of computing all
computable universes!
speed prior logo

Speed Prior

Former or later such observers will build their own computers and nested virtual worlds and extrapolate from there and get the idea their "real" universe is a "simulation" as well, speculating their God also suffers form resource constraints. This will naturally lead them to the Speed Prior [2, 4] which assigns low probability to universes that are hard to compute. Then they will make non-traditional Speed Prior-based predictions about their future. Shouldn't we do so, too? Compare [4, 5].

Fibo-
nacci
web
design

2007

Here is what the leading European news magazine Der SPIEGEL wrote about Schmidhuber's simple program for all universes (30/2002, p 133-134).

Such wild ideas have recently attracted quite some attention - check out the following links!

1. Wei Dai's searchable "everything" mailing list archive.

2. Plamen Petrov's digital physics site.

3. Ed Fredkin's digital mechanics site.

4. Max Tegmark's TOE site

5. Comments on Wolfram's 2002 book.

6. Seth Lloyd's 1999 paper on the universe as a quantum computer.

7. A 2 page interview by the Aargauer Zeitung: PDF (in German, April 2008).
.


The work mentioned above focused on description size and completely ignored computation time. From a pragmatic point of view, however, time seems essential. For example, in the near future kids will find it natural to play God or "Great Programmer" by creating on their computers their own universes inhabited by simulated observers. But since most computable universes are hard to compute, and since resources will always be limited despite faster and faster hardware, self-appointed Gods will always have to focus on relatively few universes that are relatively easy to compute. So which is the best universe-computing algorithm for any decent "Great Programmer" with resource constraints? It turns out there is an optimally fast algorithm which computes each universe as quickly as this universe's unknown (!) fastest program, save for a constant factor that does not depend on universe size. In fact, this algorithm is essentially identical to the one on page 1 of Schmidhuber's above-mentioned 1997 paper [1].

Given any limited computer, the easily computable universes will come out much faster than the others. Obviously, the first observers to evolve in any universe will find themselves in a quickly computable one.



Wei Dai's "everything mailing list". Wei Dai has set up a mailing list for discussing such ideas. Here is his 1998 message (links updated May 2008).
From: Wei Dai, Thu, 15 Jan 1998
Subject: ANNOUNCE: the "everything" mailing list

You are invited to join a mailing list for discussion of the idea that all possible universes exist. Some possible topics of discussion might include:

  • What is the set of all possible universes?
  • What is a reasonable prior/posterior distribution for the universe that I am in?
  • Why do we believe that both the past and the future are non-random, but the future is more random than the past?
  • Before observing anything about the universe, should we expect it to have (infinitely?) many observers?
  • How can we/should we predict the future and postdict the past?
  • Here are some papers that can serve as a basis for the discussion:

  • "Investigations into the Doomsday Argument", Nick Bostrom
  • "A Computer Scientist's View of Life, the Universe, and Everything", Juergen Schmidhuber
  • Is ``the theory of everything'' merely the ultimate ensemble theory?", Max Tegmark
  • (Postings referring to Schmidhuber's work can be found here.)


    Juergen Schmidhuber  at TEDx UHasselt, talking about the computational multiverse
    15 Mar 2013: Transcript (at Kurzweil AI) of TEDx talk at UHasselt, Belgium: In the beginning was the code. This is about the fastest way of computing all logically possible universes, and what it implies for our future.






    JS  in
    13 June 2012: JS in the US TV Premiere of Through the Wormhole with Morgan Freeman on the Science Channel.