. 

Algorithms Special Issue (2010)


. 
. 
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. 7579, 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, JulyAugust 2006.
HTML.
[5]
J. Schmidhuber.
The New AI: General & Sound & Relevant for Physics
(HTML).
TR IDSIA0403.
In B. Goertzel and C. Pennachin, eds.: Artificial
General Intelligence, p. 175198, 2006.
PDF.
PS.
PDF.
HTML.
ArXiv:
cs.AI/0302012.
[4]
The Speed Prior: A New Simplicity Measure
Yielding NearOptimal 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 216228. 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):587612, 2002.
PDF.
PS.
Based on sections 25 of ref [2] below.
[2]
Algorithmic theories of everything
(2000).
PDF.
HTML.
ArXiv:
quantph/ 0011122.
Led to refs [3] and [4] above.
[1]
A Computer Scientist's View of Life, the Universe, and Everything.
LNCS 201288, Springer, 1997 (submitted 1996).
HTML (1996).
PS.
PS.GZ.
PDF.
(Later copy in ArXiv.)
.


Jürgen Schmidhuber's
Computable Universes & Algorithmic Theory of Everything: The Computational Multiverse
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 complexitybased 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.




. 


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 limitcomputable
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 25 led to
generalizations of Kolmogorov's and Solomonoff's
complexity and probability measures [3,4].




There is a fastest way of computing
all computable universes!
 
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
nontraditional
Speed Priorbased predictions
about their future. Shouldn't we do so, too?
Compare [4, 5].




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, selfappointed Gods will always have to
focus on relatively
few universes that are relatively easy to compute.
So which is the best universecomputing 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 abovementioned
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 nonrandom, 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.)


