# Law without law: from observer states to physics via algorithmic information
theory

Markus P. Müller  Institute for Quantum Optics and Quantum Information,
Austrian Academy of Sciences, Boltzmanngasse 3, A-1090 Vienna, Austria
Perimeter Institute for Theoretical Physics, Waterloo, ON N2L 2Y5, Canada

(July 26, 2019)

###### Abstract

According to our current conception of physics, any valid physical theory is
supposed to describe the objective evolution of a unique external world.
However, this condition is challenged by quantum theory, which suggests that
physical systems should not always be understood as having objective
properties which are simply revealed by measurement. Furthermore, as argued
below, several other conceptual puzzles in the foundations of physics and
related fields point to limitations of our current perspective and motivate
the exploration of an alternative: to start with the first-person (the
observer) rather than the third-person perspective (the world).

In this work, I propose a rigorous approach of this kind on the basis of
algorithmic information theory. It is based on a single postulate: that
_universal induction_ determines the chances of what any observer sees next.
That is, instead of a world or physical laws, it is the local state of the
observer alone that determines those probabilities. Surprisingly, despite its
solipsistic foundation, I show that the resulting theory recovers many
features of our established physical worldview: it predicts that it appears to
observers _as if there was an external world_ that evolves according to
simple, computable, probabilistic laws. In contrast to the standard view,
objective reality is not assumed on this approach but rather provably emerges
as an asymptotic statistical phenomenon. The resulting theory dissolves
puzzles like cosmology’s Boltzmann brain problem, makes concrete predictions
for thought experiments like the computer simulation of agents, and suggests
novel phenomena such as “probabilistic zombies” governed by observer-dependent
probabilistic chances. It also predicts some basic phenomena of quantum theory
(Bell inequality violation and no-signalling) and suggests a novel
“algorithmic” perspective on the foundations of quantum mechanics.

###### Contents

  1. 1 Introduction
  2. 2 Algorithmic probability
  3. 3 Postulates of an incomplete theory
    1. 3.1 Algorithmic priors and levels of indeterminism
    2. 3.2 Encoding invariance
    3. 3.3 Why use algorithmic probability?
  4. 4 Emergence of an external physical world
    1. 4.1 Warm-up: persistence of regularities
    2. 4.2 Computable laws and the external process
  5. 5 The rise and fall of objective reality
    1. 5.1 Asymptotic coherence of ${\mathbf{P}}_{\rm 1st}$ and ${\mathbf{P}}_{\rm 3rd}$
    2. 5.2 Probabilistic zombies
    3. 5.3 Subjective immortality
  6. 6 Application to exotic scenarios
    1. 6.1 Dissolving the Boltzmann brain problem
    2. 6.2 Simulating agents on a computer
  7. 7 Why the quantum?
  8. 8 Conclusions
  9. A Appendix

##  1 Introduction

Theoretical physics is more than just a fixed framework that allows us to
predict measurable quantities. Ever since the first philosophers have wondered
what our universe is made of, the very nature of the questions that we ask in
physics has been continuously evolving. Novel discoveries and problems have
led to completely new concepts that did not even make sense within earlier
theories. For example, the problem of ether and of the Lorentz transformations
in electrodynamics have ultimately led us to a framework (relativity) in which
the structure of spacetime itself is dynamical, which is an idea that could
not even have been formulated within Newtonian mechanics.

The starting point of this work is the hypothesis that we are perhaps at a
point where we may want to consider another substantial revision of some
traditional aspects of our worldview, at least in certain contexts. We are
facing several conceptual problems, some of them of enormous importance, for
which systematic problems and difficulties arise when we try to address them
with standard approaches. While some of these questions are simply free-
floating expressions of human curiosity (like _“Why are there simple laws of
physics at all?”_), others have emerged as notorious and persistent problems
in physics and related areas. They seem to show us in a rather annoying way
that there is something that we fundamentally do not understand (see Table 1
for an overview).

For example, consider some questions that are currently being discussed in the
context of cosmology: what if the universe is really large (as in eternal
inflation) and contains a multitude of copies of every observer AguirreTegmark
? How can we assign probabilities to properties of “possible worlds” Linde ?
What if thermal fluctuations produce a massive amount of randomly appearing
“Boltzmann brains” Albrecht2002 ; AlbrechtSorbo2004 ; Nomura  — can we use the
assumption that we are _not_ the result of such fluctuations to constrain our
cosmological models? Independently, philosophers are discussing questions
related to agents or observers that seem at first sight to be of a very
different category, like: What happens if we simulate an intelligent agent on
a computer — would the simulation be “alive” Bostrom ?

Even though these puzzles seem to be of quite different nature at first sight,
they do have a common core — they are all specific instances of the question:
“What will I see next?” In the empirical regime, _physics_ allows us to answer
this question, at least probabilistically. For example, if we send a photon to
a half-silvered mirror in the laboratory, then quantum physics tells us that
we will see the photon being transmitted (or rather hear a specific detector
click) with $50\%$ probability. But we can ask this question also in exotic
situations, some of which are listed in Table 1. For example, if we are
promised to be scanned in all detail to a computer, and then to be simulated
in one (or even many different) virtual worlds, will we “wake up” in a
simulation (and, if so, in which one)? In this context, it seems inappropriate
to try to answer the question in boldface solely on the basis of information
about the detailed physical composition of body or computer. Instead, the
question now seems to fall into the realm of the philosophy of mind.

Similarly, if we assume the validity of a cosmological model predicting a
universe with a large number of Boltzmann brains, does it make sense for _me_
to hold a degree of belief on whether _I am actually one of them_? Can we
assign a meaningful probability to the possibility that _what I see next_ is
the strange experience of one of those fluctuating beings, perhaps suddenly
realizing that something is very strange before disappearing? Conversely, can
we use the empirical fact that _this is not what we see_ to rule out some
cosmological models? The very existence of controversy among cosmologists
regarding these questions tells us that we have no idea how to approach them
in a conclusively coherent way.

From this perspective, it seems odd that a single unifying question has to be
approached with so different methods in the different regimes — physics,
philosophy, or outright speculation. But is this actually a fair comparison?
Isn’t physics, after all, more concerned with the question of “What is the
world like?” rather than “What will I see next?” Not if we live in a quantum
world. Ultimately, the formalism of quantum theory tells us the probabilities
of outcomes of experiments, i.e.  _the chances of what to see next_ , given
the physical context. In particular, due to results like Bell’s theorem
Bell1964 ; Bell1966 , it is provably inconsistent to assume that measurements
simply uncover preexisting unknown facts of the world, without sacrifizing
other important principles of physics like locality. We should not think of
the wave function as the “configuration of the world” in a naive sense, but
rather as a catalogue of expectations about what an agent will see next.
Therefore, quantum theory gives us a physical motivation to regard the
question in boldface above as more fundamental than the question of what the
world is like.

  * •

Quantum theory. “Unperformed experiments have no results” PeresNoResults ;
FuchsSchack ; measurement problem FuchsQFQIT ; no-go results about observer-
independent facts BruknerNogo ; Bong .

  * •

Cosmology. Boltzmann brain problem Albrecht2002 ; AlbrechtSorbo2004 ; self-
locating uncertainty AguirreTegmark ; measure problem Linde .

  * •

Philosophy of mind / future technology. _“Are you living in a computer
simulation?”_ Bostrom , puzzles of personal identity like _“A Conversation
with Einstein’s Brain”_ in Hofstadter’s and Dennett’s “The Mind’s I”
HofstadterDennett , or Parfit’s _teletransportation paradox_ Parfit .

  * •

Fundamental curiosity. Why is there a “world” with “laws of nature” in the
first place?

$\longrightarrow$ start with conditional probabilities

$\mathbf{P}(\mbox{next observer state }|\mbox{ current observer state}).$

TABLE 1. Some enigmas that motivate the approach of this paper. As explained
in more detail in the main text, even though these conceptual puzzles are
rooted in different fields, they have a common feature: they can all in
principle be reformulated in terms of the question of _what is the probability
of my future state, given my current state_ (including my momentary
observations and memory, conscious or not). This motivates the attempt to
formulate a framework for which these first-person conditional probabilities
are fundamental, and which does not assume that they come from an external
world.

Given that this single question appears in so many instances in different
fields — could there be a single, unified approach or theory that _answers
this question in all contexts uniformly_? Such a theory would have an
important advantage: while most ad hoc claims about problems like the brain
emulation question above do not seem to be directly amenable to empirical
testing111After all, we cannot directly empirically test any predictions of
the form “Yes, if we do a simulation of this or that kind, then the simulated
mind _really has_ an inner life in the same way that we do”. Simply observing
the simulated mind, or asking it, will not allow us to draw any ultimate
conclusions; see e.g. the philosophical discussion of “zombies” SEP . Of
course we can (and should) study other aspects of this problem empirically,
e.g. via neuroscience., the hypotheses of such a unified approach about these
exotic phenomena could be put to an indirect test. Namely, if that theory made
in principle successful empirical predictions in the regime of physics, then
this would justifiably increase our trust in its predictions in the more
speculative regime.

The goal of this work is to provide a proof of principle that we can indeed
have a theory222Note that this is _not_ supposed to be a “theory of
everything”; in fact, the theory predicts its own limitations. By
construction, it will have to say nothing about most things. As an obvious
example, it will not be useful for the search for a theory of quantum gravity.
of this kind — one that is simple, rigorous, and well-motivated. We arrive at
such a theory quite naturally by following a few well-motivated assumptions.
Our first assumption is to committ to the _first-person perspective of
observers_ 333In line with Rovelli Rovelli , here the word “observer” is by no
means restricted to _human_ observers, and it is not (at least not directly)
related to the notion of “consciousness”. The question of consciousness is
irrelevant for this paper; my notion of “first-person perspective” is by no
means meant to be equivalent to consciousness. The former (but probably not
the latter) describes a very general, technically formalizable notion that is
agnostic about the question “what that perspective really feels like”. As a
rough analogy, note that computer science can reason about the information
content of a painting (say, after it is digitized and saved on a hard drive)
without the need to decide what it is supposed to depict, or whether it is
“beautiful”. as being fundamental. In more detail, we start with what we call
the “observer state”: a mathematical formalization of the information-
theoretic state of the observer, including its current observations and its
memory (conscious and unconscious). This will be our primitive notion, and we
will drop all assumptions of an “external world”. A moment’s thought shows
that such a move is unavoidable if we want to address questions like those
mentioned above. For example, if we ask _“why is there a “world” with “laws of
nature” at all?_ , then we must have a starting point that does not assume the
existence of such a world from the outset. Similarly, if we do not think that
detailed insights into physical properties of the world can help us resolve
puzzles like Parfit’s teletransportation paradox, then we must be able to
argue without these ingredients.

Given such a notion of “observer state”, we can formulate a possible answer to
the question of “what the observer will see next”: namely, we would like to
write down some notion of propensity, or chance,

${\mathbf{P}}(\mbox{next observer state}\,|\,\mbox{current observer state}).$
(1)

Our second assumption is that this chance Myrvold  always exists, and that
there is a mathematical object ${\mathbf{P}}$ that formalizes it. For the
moment, think of ${\mathbf{P}}$ as a probability distribution; later on, its
role will in fact be played by a more general object (a countable set of
asymptotically equivalent distributions). Consider the following example.
Suppose that $x$ describes the state of an observer who knows that she will
now be put to sleep, scanned, and simulated in a computer. Let $y$ be the
observer state that she would have at the first moment of computer simulation.
Then what we assume here is that there is in fact an “objective chance”
${\mathbf{P}}(y|x)$ that the observer will “wake up” in the simulation.
Moreover, this notation implies that this chance is _independent of all other
“facts of the world”_ — it really only depends on the state of the observer.

It is important to understand that ${\mathbf{P}}$ is _not_ meant to represent
the observer’s degree of belief. As a colourful and imprecise example, suppose
that $x$ describes the state of a little insect that is crawling across the
edge of a table. Then (we think that) there is a large chance
${\mathbf{P}}(y|x)$ of transitioning into a state that experiences falling,
even if the insect is too stupid to hold beliefs (let alone to compute
probabilities). Moreover, the observer state should be interpreted as
encompassing all information “contained in” the observer, not just what the
observer is consciously aware of. In this example, $x$ could contain enough
information from the insect’s nervous system to indicate _in principle_ the
presence of the table’s edge, even if the insect is not aware of it.

Finally, to obtain a complete theory, we have to concretely postulate what
${\mathbf{P}}$ should be. As mentioned above, ${\mathbf{P}}$ will be something
like (but not quite) a probability distribution. In order to obtain a
meaningful, mathematically formalized, objective theory, it should _not_ be
necessary to determine what it “feels like” to be in a particular observer
state $x$ in order to determine ${\mathbf{P}}(y|x)$. Instead,
${\mathbf{P}}(y|x)$ should only depend on the abstract information content of
$x$ and $y$, and not on questions of qualia. As we will explain in Section 2
and motivate in detail in Section 3, we will here postulate that
${\mathbf{P}}$ should express some form of “universal induction”:
${\mathbf{P}}(y|x)$ is large if an external rational agent with complete
knowledge of $x$ would be led to predict $y$. This will lead us to claim that
${\mathbf{P}}$ is some version of _algorithmic probability_. Such
${\mathbf{P}}$ is related to description length: the more _compressible_ the
conceivable future state $y$ (given the current state $x$), the more likely.
Thus, in the approach of this paper, answering the brain emulation question
above boils down to estimating the algorithmic complexities of the simulated
observer states. We study this problem in detail in Subsection 6.2.

The theory is introduced in two successive steps, distinguished by their color
shading:

I. | Mathematical formulation
---|---
| Sections 2 (algorithmic probability) and 3.
II. | Predictions of the theory
| Sections 4–7.

Section 2 will introduce the notions of observer states and algorithmic
probability. Section 3 spells out the postulates of this paper’s approach, and
motivates why algorithmic probability is our measure of choice.

The second part reconstructs aspects of physics from the postulates, and uses
them to address some of the puzzles of Table 1. While our methodological
starting point is in some sense solipsistic, Section 4 shows how we can
nevertheless understand the existence of an external world with simple
computable probabilistic laws of physics as a _consequence_ of this framework.
Furthermore, Section 5 proves that we also obtain an emergent notion of
objective reality. Subsections 5.2 and 5.3 argue, however, that there are
extreme situations in which objective reality breaks down, leading to the
phenomena of “probabilistic zombies” and “subjective immortality”. Section 6
describes how the Boltzmann brain problem gets dissolved, and what we can say
about the computer simulation of agents. Finally, Section 7 shows that some
basic phenomena of quantum theory are to be expected in this framework, before
we conclude in Section 8.

##  2 Algorithmic probability

There are two main notions mentioned in the introduction that we have to
discuss in all mathematical details: the _state_ of an observer, and the
chance ${\mathbf{P}}$. We will begin by stipulating that observer states shall
be modelled by the _finite binary strings_ :

${\mathcal{S}}=\\{\varepsilon,0,1,00,01,10,11,000,\ldots\\}.$

The _length_ of a string $x\in{\mathcal{S}}$ will be denoted $\ell(x)$; for
example $\ell(11)=2$. The symbol $\varepsilon$ denotes the empty string of
length zero. We will assume that _every possible observer state corresponds to
a binary string; and, vice versa, to every binary string there is a
corresponding observer state, i.e. “state of being” of a conceivable
observer_. As explained in the introduction, we should think of an observer
state as an exhaustive description of an observer’s memory (conscious or
unconscious) and momentary observations — all her “locally accessible
information”. Naively, think of a raw dump of the information-theoretic
content of a human brain at some moment in time, scanned up to all
functionally relevant detail. Now, this is not an exact interpretation. To
what detail exactly are we supposed to scan? Where exactly do we put the
boundaries of the brain? In the following, we will see that we do not need to
answer these questions to construct our theory and to extract its predictions.
Moreover, the _interpretation_ of an observer state will gradually become more
clear in the course of construction of the theory.

It is important to understand that most observer states are completely
unrelated to states of humans or animals. (This is a truism as obvious as
stating that “almost all theoretically possible digital pictures do not show
anything that you are familiar with”.) We have to, may, and will ignore
questions of qualia like “what does it feel like to be in state $x$”?
Moreover, the actual zeroes and ones in an observer state do not carry any
meaning in isolation. This is comparable to, say, the theory of general
relativity, where coordinates of spacetime points like $x=(0,0.3,-0.14,1.25)$
do not carry any meaning in themselves, but only _relative to a choice of
coordinate system_. While general relativity allows for a mostly arbitrary
choice of coordinate system, we will see in Section 3 that we also have a
mostly _arbitrary choice of encoding_ , and changing the encoding will change
the bit string.

Since observer states are discrete, it makes sense that the state of the
observer changes in discrete (subjective) time steps. That is, every observer
will be in some state now, in another state next, and so on. This leads us to
study transition probabilities of the form ${\mathbf{P}}(y|x)$ (as indicated
in (1)). Before trying to define these, however, it turns out to be much
easier to study unconditional probabilities ${\mathbf{P}}(x)$ of bit strings
$x$: we can apply known results from algorithmic information theory to define
and analyze these.

To this end, let us start with some intuition. We would like to postulate a
probability measure ${\mathbf{P}}$ that determines the chances of what
observers see. How can we do so, without making arbitrary choices or smuggling
known facts of physics into the definition? I will argue in the following that
a version of _algorithmic probability_ is a good candidate, since it uses only
structure that is unavoidably there once we start to reason logically: the
computability structure of axiomatic systems. While a more detailed discussion
of the motivation will be deferred to Section 3, this subsection will now
appeal to intuition, and at the same time derive and present a definition of
algorithmic probability.

Let us step back for a moment and recall some basic ideas from probability
theory. When students start to learn stochastics at school, often the first
example they discuss is that of an “urn”, containing balls that have different
colors, and of some experimenter drawing one of the balls at random. In our
case, the differently colored balls correspond to the observer states, i.e.
the finite binary strings. Also, bit strings are purely mathematical objects,
so in some sense, mathematics itself represents the analog of the urn, or,
say, the formal axiomatic system that is used to define the notion of a
“binary string”. But what corresponds to the act of “drawing” such a
mathematical object at random?

Intuitively, the concrete mechanism of drawing determines the resulting
probability distribution. If the urn contains two red balls and a green ball,
say, then the chance of drawing the green ball will only be close to
$\frac{1}{3}$ if the experimenter has equal access to all the balls (for
example, none of the balls lies at the bottom of the urn and cannot be reached
by the experimenter), if she moves her arm uniformly inside the urn in a
pseudo-random fashion, and if she does not see, feel or detect the color of
the balls in any way444What I write here has only motivational value; I do not
claim to say anything profound about the foundations of probability theory..
On the other hand, if one of the balls is in some sense “easier to draw” (say,
there are $3$ balls, and $2$ of them are hidden in the urn’s corners), then
the chance of drawing that ball will be higher.

How can we “draw” a finite binary string? If we are looking for a “natural”
mechanism that is not just chosen arbitrarily from all conceivable mechanisms,
then we should only use structures that are given to us apriori — that is,
ones that are supplied by mathematics itself. Mathematics constitutes the
“urn” that contains the finite binary strings, and supplies mechanisms for
drawing them. In a mathematical formal system, we can “draw” a mathematical
object by describing it. That is, we can write down a definition, based on the
axioms of our formal system, and thereby selecting a mathematical object from
the “urn” of all mathematical objects.

Thus, our random experiment might be performed by a mathematician, equipped
with paper and pencil, who draws finite binary strings by describing them.
Some strings are much easier to describe than others, even if they contain
more bits. For example, the binary string

$x:=\underbrace{00000\ldots 0}_{\mbox{a million zeroes}}$

is easy to describe — in fact, we have just described it (and it remains
easily describable even if we demand a more formally sound way, say, a
definition according to the rules of a fixed formal system). Similarly, it is
easy to describe the string

$x_{\pi}:=0010001000011111101\ldots$

containing the first $10^{6}$ binary digits of $\pi$. Some strings are much
more difficult to describe, like

$x_{c}:=010010100010000011110\ldots$

which is a concrete structureless string of $1000$ bits, generated by a
thousand tosses of a fair coin. The simplest way to describe the string by
mathematical means seems to be to write it down bitwise, which arguably needs
more effort (and more paper space) than the previous two strings.

So the strings $x$ and $x_{\pi}$ seem to be easier to describe, and, according
to our urn metaphor, easier to “draw” than $x_{c}$, for example. Hence they
should have larger probability with respect to the distribution that we are
looking for.

But how can we formalize this idea? How can we “describe a string at random”
and get a meaningful probability distribution? The idea of a mathematician,
randomly writing down definitions on a piece of paper, is clearly not formal
enough to determine a well-defined distribution.

It turns out that there is a precise formal definition of this very idea,
which is known as _algorithmic probability_. The main insight is as follows:
every step of formal manipulation performed by the mathematician can also be
done by a universal computing machine. Thus, instead of asking how easy it is
for a mathematician to write down a definition of a binary string, we can ask
how easy it is to program a universal computer to output the corresponding
string.

I will now give a brief introduction to algorithmic information theory and
probability which is mainly based on the book by Hutter Hutter . I will be
concise and focus only on those aspects that are relevant for the present
paper, assuming that the reader is familiar with some basic notions of
theoretical computer science (e.g. the Turing machine, the halting problem,
and computability). A more detailed and pedagogical introduction can be found
in the book by Li and Vitányi LiVitanyi , see also Chaitin .

One of the basic models of computation is the Turing machine CoverThomas ,
consisting of several (input, work and output) tapes carrying some data given
by bits, a finite state machine, and some read-write-heads pointing to a
single cell on each tape and giving the position where to read or write next.
In accordance with Hutter , we shall only consider Turing machines with one
unidirectional input tape, one unidirectional output tape (to be generalized
later), and several bidirectional work tapes. “Input tapes are read only,
output tapes are write only, unidirectional tapes are those where the head can
only move from left to right. All tapes are binary (no blank symbol), work
tapes initially filled with zeros.”

Now we distinguish two different possible events: first, the Turing machine
$T$ might halt and output a fixed, finite binary string $x\in{\mathcal{S}}$.
Second, the Turing machine $T$ might compute a possibly infinite bit string
without ever halting; in this case, we may still observe that the output
string starts with a finite bit sequence $x\in{\mathcal{S}}$. This is due to
the fact that the output tape is assumed to be unidirectional. We use the
definition given in Hutter :

_Monotone TM. We say $T$ outputs/computes a string starting with
$x\in{\mathcal{S}}$ on input $p\in{\mathcal{S}}$, and write $T(p)=x*$ if $p$
is to the left of the input head when the last bit of $x$ is output ($T$ reads
all of $p$ but no more). $T$ may continue operation and need not halt. For
given $x$, the set of such $p$ forms a prefix code. We call such codes $p$
minimal programs._

Now we are ready to define the crucial concepts of Kolmogorov complexity and
algorithmic probability:

######  Definition 2.1 (Algorithmic probability and complexity).

Let $T$ be any monotone Turing machine. The _monotone complexity_ or
(monotone) Kolmogorov complexity of a string $x\in{\mathcal{S}}$ with respect
to $T$ is given by

${\rm Km}_{T}(x):=\min\\{\ell(p)\,\,|\,\,T(p)=x*\\}$

or by $\infty$ if no such program $p$ exists. Moreover, define the
_algorithmic probability_ that $T$ outputs some string that starts with
$x\in{\mathcal{S}}$ by

$\mathbf{M}_{T}(x):=\sum_{p:T(p)=x*}2^{-\ell(p)}.$

Since the set of programs $p$ such that $T(p)=x*$ is prefix-free, it follows
from the Kraft inequality that $\mathbf{M}_{T}(x)\leq 1$ for all $x$. This
expression can be interpreted as the probability that $T$ outputs a string
that starts with $x$ if the input is chosen by tossing a fair coin. In more
detail, $\mathbf{M}_{T}$ is a _semimeasure_ in the sense of the following
definition:

######  Definition 2.2 (Measures and semimeasures Hutter ).

A function $m:{\mathcal{S}}\to{\mathbb{R}}_{0}^{+}$ is called a _semimeasure_
if $m(\varepsilon)\leq 1$ and $m(x)\geq m(x0)+m(x1)$, and a _probability
measure_ if equality holds in both cases.

We define the conditional (semi)measure as

$m(y|x):=\frac{m(xy)}{m(x)}\quad(x,y\in{\mathcal{S}})$

if $m(x)\neq 0$, where $xy$ denotes the concatenation of $x$ and $y$.

One of the most important facts in computer science is the existence of
“universal computers” that are capable of simulating every other computer.
That is, if $U$ is a universal computer and $T$ an arbitrary computer, then
every program for $T$ can easily be “translated” into a program for $U$ which
generates the same output:

######  Theorem 2.3 (Universal Turing machine Hutter ).

There exists a universal monotone Turing machine $U$ which simulates every
monotone Turing machine $T$ in the following sense: to every $T$, there is a
finite binary string $x_{T}\in{\mathcal{S}}$ such that

$T(p)=U(x_{T}p),$

where $x_{T}p$ denotes the binary string obtained by concatenating $x_{T}$ and
$p$.

Since a universal Turing machine $U$ can simulate every other machine, its
monotone complexity measure ${\rm Km}_{U}$ is “optimal” in the sense that
${\rm Km}_{U}(x)\leq{\rm Km}_{T}(x)+c_{T}$ for every Turing machine $T$, where
$c_{T}\in{\mathbb{N}}$ is a constant that does not depend on $x$. A similar
inequality holds for algorithmic probability: we have

$\mathbf{M}_{U}(x)\geq c^{\prime}_{T}\cdot\mathbf{M}_{T}(x),$ (2)

where $c^{\prime}_{T}>0$ is another constant not depending on $x$. In
algorithmic information theory, these optimality inequalities are then used as
a motivation to choose an arbitrary universal Turing machine $U$, and to
define all the relevant quantities with respect to that machine:

######  Definition 2.4.

Fix any universal monotone Turing machine $U$, and set ${\rm Km}(x):={\rm
Km}_{U}(x)$ and $\mathbf{M}(x):=\mathbf{M}_{U}(x)$.

The resulting measures do not depend too much on the choice of $U$; in
particular, if $U$ and $W$ are both universal, then $\mathbf{M}_{U}$ and
$\mathbf{M}_{W}$ can be estimated against each other in both directions by a
multiplicative constant as in (2). This kind of “weak” machine-independence
will be of high relevance for the theory of this paper, as we will discuss in
Section 3.

Figure 1: Sketch of a monotone Turing machine $T$. The machine reads some
(possibly infinite) binary input string, here starting with $0110010100$, and
the snapshot depicts the output relation $T(01)=0011*$.

An characteristic property of $\mathbf{M}$ is its universality:

######  Theorem 2.5 (Universal enumerable semimeasure Hutter ).

If $T$ is a monotone Turing machine then $\mathbf{M}_{T}$ is an enumerable
semimeasure. Vice versa, for every enumerable semimeasure $m$ there exists a
monotone Turing machine $T$ with $\mathbf{M}_{T}(x)=m(x)$ for all non-empty
strings $x\in{\mathcal{S}}$. Moreover, if $U$ is universal, then
$\mathbf{M}_{U}$ is a universal enumerable semimeasure; that is, for every
enumerable semimeasure $m$, it holds

$\mathbf{M}_{U}(x)\geq 2^{-\mathrm{K}_{U}(m)}\cdot m(x)$

for all $x\in{\mathcal{S}}$, where $\mathrm{K}_{U}(m)$ denotes the length of
the shortest binary string that makes $U$ emulate any monotone Turing machine
which has $m$ as its semimeasure, i.e.

$\mathrm{K}_{U}(m)=\min\\{\ell(x)\,\,|\,\,\forall p:U(xp)=T(p)\mbox{ and
}\mathbf{M}_{T}=m\\}.$

This definition uses the notion of _enumerability_ of a function
$f:{\mathcal{S}}\to{\mathbb{R}}$. Suppose we have a computable function
$\Phi:{\mathcal{S}}\times{\mathbb{N}}\to{\mathbb{R}}$ such that
$\lim_{n\to\infty}\Phi(x,n)=f(x)$ and $\Phi(x,n)\leq\Phi(x,n+1)$ for all
$x\in{\mathcal{S}}$ and $n\in{\mathbb{N}}$. Then $f$ can be approximated from
below by a single computer program (computing $\Phi$), without necessarily
knowing how close the approximation will be to the true value $f(x)$. In this
case $f$ is called _enumerable_. If additionally $(-f)$ is enumerable as well,
then we can estimate the error of approximation for finite $n$ by computably
determining a finite interval that contains $f(x)$. If this is the case, $f$
is called _computable_.

While $\mathbf{M}=\mathbf{M}_{U}$ is only a semimeasure, we can define its
_Solomonoff normalization_ LiVitanyi

${\mathbf{P}}_{U}(\varepsilon):=1,\quad{\mathbf{P}}_{U}(xa):={\mathbf{P}}_{U}(x)\cdot\frac{\mathbf{M}_{U}(xa)}{\sum_{b}\mathbf{M}_{U}(xb)}\quad(a\in\\{0,1\\})$

to obtain a _measure_ that shares many (but not all) desirable properties with
$\mathbf{M}$. We also define ${\mathbf{P}}:={\mathbf{P}}_{U}$, where $U$ is
our choice of reference universal computer. It is easy to see that
$\mathbf{M}_{U}$ and ${\mathbf{P}}_{U}$ are related by the inequalities

${\mathbf{P}}_{U}(x)\geq\mathbf{M}_{U}(x),\quad{\mathbf{P}}_{U}(y|x)\geq\mathbf{M}_{U}(y|x).$

This ${\mathbf{P}}$ will be our measure of choice, and will be called
“algorithmic probability” in the following. We are now ready to formulate the
basic postulates of the theory of this paper.

##  3 Postulates of an incomplete theory

Let me clarify right away that the theory of this paper will not satisfy all
the desirabilities that have been formulated in the introduction. Namely, what
we would _like_ to have is a theory that satisfies the following Postulates:

######  Postulates 3.1 (Desired postulates; not used in that form).

  * (i)

Observer states. Having a first-person perspective means to be in some
observer state at any given (subjective) moment. The observer states are in
computable one-to-one correspondence with the finite binary strings.

  * (ii)

Dynamics. Being in some observer state $x$ now, there is a well-defined chance
of being in some other observer state $y$ next. It is denoted

${\mathbf{P}}_{\rm des}(y|x),$ (3)

and is given by a variant of algorithmic probability — in more detail, by a
countably-infinite set of algorithmic priors (one for every universal
machine).

  * (iii)

Predictions. The predictions of the theory are those that are identical for
every choice of algorithmic prior. They follow from (i) and (ii) alone; no
external world, laws of physics or other ingredients are fundamentally
relevant. “Now” and “next” are understood as purely first-person notions, not
related to any external notion of time or clock.

Before explaining which one of these postulates has to be modified and why,
let me give some more intuition on the worldview that they express. The
formulation itself seems solipsistic in some sense: it talks about what it
means to “have a first-person perspective”. In this sense, it talks about the
“I”: I am currently in some state $x$, and then I will be in some other state
$y$. So who is this “I”? What about “you” or “them”, i.e. other observers? Or
is there only ever one observer?

We will address these questions in more detail in the following sections, when
the ontology of the theory will become gradually more clear while working out
the postulates’ consequences. A preliminary answer is that the postulates can
be used by _everybody_ : they allow every observer in principle to make an
educated guess of what happens to them next, _if_ they hold some
knowledge555Note that this knowledge is typically not complete: it is hard for
an observer to hold a complete description of itself. It even seems like a
kind of Gödelian impossibility in principle. of their current observer state
$x$. This is a bit similar to the tenets of Bayesianism, which can be used by
_everybody_ to make rational bets on their future. Nonetheless, the
probabilities ${\mathbf{P}}(y|x)$ are understood as actual chances, not as
degrees of belief.

In the theory described by these postulates, there is no fundamental notion of
an “observer”, but only of “observer _states_ ”. That is, observers are not
material objects in some universe which could be distinguished and counted, at
least not in all cases. This is perhaps not so surprising, given that we have
a theory that intends to say something meaningful about puzzles like Parfit’s
teletransportation paradox or about “copying” observers. For a colorful
example, think of the “Back to the Future” movie series, in which the main
protagonist (Marty McFly) meets his older self in the future. Is this now one
observer, or two? This is a fundamentally meaningless question. In any case,
our theory will allow situations that can best be described as “encountering
other observers”, and we will discuss these situations in detail in Section 5.

So when did the observer start? When did she hold her first observer state?
Will she not die some time? Indeed, the postulates above say that the answer
to the latter question is negative — the observer will follow a never-ending
Markovian process. It also doesn’t make sense to talk of a “beginning”. Any
notions of this kind — and of an external world that seems to have begun in a
Big Bang a long time ago — will have to be reconstructed from the postulates
alone. The exciting news is that _this can in fact be done to some extent_.
That is, we will understand “why” observers will see something like an
external world “around them” as a _consequence_ of these postulates.

Before discussing Postulate (iii) in more detail, let me explain why,
unfortunately, algorithmic probability does not formalize all the intuitive
properties that the desired ${\mathbf{P}}_{\rm des}$ in (3) above should have.
Intuitively, if an observer is in state $x$, then she can transition into
another state $y$ _that may hold more or less information than $x$_. In
particular, it is possible for observers to “forget” information: sometimes,
memory is erased, and our next observer state $y$ does not contain full
information on the previous state $x$. This seems natural and unavoidable. On
the other hand, conditional algorithmic probability
${\mathbf{P}}(y|x)={\mathbf{P}}(xy)/{\mathbf{P}}(x)$ is defined as the
probability that the next observer state will be $xy$, given that it is now
$x$. In other words, algorithmic probability defines a situation in which _an
observer never forgets anything_. This will define the postulates that we are
actually working with — and, as expressed below, it will therefore be an
approximation to our desired postulates which applies whenever memory erasure
can be neglected:

######  Postulates 3.2 (Deficient postulates as actually used).

  * (i)

Observer states. Having a first-person perspective means to be in some
observer state at any given (subjective) moment. The observer states are in
computable one-to-one correspondence with the finite binary strings.

  * (ii)

Dynamics. Being in some observer state $x$ now, there is a well-defined chance
of being in some other observer state $xa$ next, where $a\in\\{0,1\\}$ is a
bit. It is given by

${\mathbf{P}}_{U}(a|x),$ (4)

i.e. the conditional version of algorithmic probability ${\mathbf{P}}$ as
defined after Theorem 2.5. Here, $U$ is a universal monotone Turing machine
that can be chosen arbitrarily, but has to be fixed.

  * (iii)

Predictions. The predictions of the theory are those that are identical for
every choice of universal machine $U$. They follow from (i) and (ii) alone; no
external world, laws of physics or other ingredients are fundamentally
relevant. “Now” and “next” are understood as purely first-person notions, not
related to any external notion of time or clock.

Interpretation: These postulates will make similar predictions as the “desired
theory” (expressed in Postulates 3.1) in those cases where the observer holds
a large amount of memory on her previous states; they will fail to do so,
however, when forgetting (information erasure) becomes relevant.

It is no loss of generality to assume that observers learn a bit at a time:
learning more than one bit can be expressed via the chain rule. If
$y=y_{1}y_{2}\ldots y_{m}\in\\{0,1\\}^{m}$, then

$\
{\mathbf{P}}(y|x)={\mathbf{P}}(y_{1}|x){\mathbf{P}}(y_{2}|xy_{1})\ldots{\mathbf{P}}(y_{m}|xy_{1}\ldots
y_{m-1}).$

It is not clear how a transition probability ${\mathbf{P}}_{\rm des}$ as in
(3) that admits forgetting should be defined; we will speculate in Section 8
that an attempt to define it should probably come with a different choice of
set of observer states, containing more structure than the set of binary
strings.

Nevertheless, my hope is that even this “deficient” set of postulates allows
us to get a glimpse on the typical properties of _theories of the kind_ as
envisaged in this paper. Indeed, even in this simplified form, we will see
that there is a wealth of surprising insights and consistent predictions that
we can extract. We will therefore work with Postulates 3.2, but always keep in
mind that forgetting, i.e. memory erasure, is not consistently treated by
these postulates.

###  3.1 Algorithmic priors and levels of indeterminism

Let us now turn to Postulate (iii), which is closely related to the following
question: _which universal machine $U$ should we use in (4)?_ At first sight,
it seems as if the infinitude of universal monotone Turing machines $U$, and
the corresponding infinitude of algorithmic probabilities ${\mathbf{P}}_{U}$,
would make the theory underdetermined. Is there a “correct” choice of $U$? Or
can we somehow average over all ${\mathbf{P}}_{U}$ in a clever way to fix the
probabilities? Unfortunately, it can be shown that the answer to this question
must be “no” as a matter of principle StatAlg ; HutterOpenProblems ; Schack97
; SterkenburgThesis , which can be related to well-known insights from
philosophy like “Goodman’s new riddle of induction” Goodman .

Instead, Postulate (iii) says that it is arbitrary which $U$ to choose — the
predictions of the theory are exactly those that are the same for every $U$.
In fact, as we shall see, there are _many interesting_ predictions that are
identical for all ${\mathbf{P}}_{U}$. This is due to the invariance property:
if $U$ and $V$ are universal monotone Turing machines, then there are
constants $0<c<C$ such that

$c\,{\mathbf{P}}_{V}(x)\leq{\mathbf{P}}_{U}(x)\leq
C\,{\mathbf{P}}_{V}(x)\mbox{ for all }x\in{\mathcal{S}}.$

But shouldn’t there be an _actual probability_ ${\mathbf{P}}(a|x)$ of the next
bit $a$, given the current observer state $x$? How can we have any predictive
power whatsoever if we can make ${\mathbf{P}}_{U}(a|x)$ equal to basically any
real number between zero and one? First of all, note that while one is allowed
to choose an arbitrary $U$, one is also _obliged to keep it fixed_. That is,
$U$ is not allowed to be changed after learning a new bit $a$, so we cannot
simply make our probabilistic predictions attain arbitrary desired numerical
values, independently over time.

To better understand the meaning of Postulate (iii), let me argue by analogy.
Imagine a physicist (the Conservative) who is familiar with Newtonian
mechanics (and perhaps its relativistic version), but nothing else. Newtonian
mechanics is a fully deterministic theory — exact knowledge of the initial
conditions allows us to predict the future behavior of any physical system
exactly. Let us denote this property by “level-0 indeterminism”. That is,
Newtonian mechanics, as a physical theory, is level-0 indeterministic (namely,
deterministic). If our world was actually exactly governed by Newtonian
mechanics, then we would live in a level-0 indeterministic world.

Now suppose that the Conservative is shocked to meet another physicist (the
Liberal) who has just proposed a physical theory which is _irreducibly
probabilistic_ : quantum theory. As the Liberal proposes, quantum theory does
not allow us to predict the outcomes of experiments with certainty, but
instead tells us _the probabilities_ of the outcomes. For example, if we send
a single photon to a half-silvered mirror, then there is a $50\%$ chance of
detecting the transmitted versus the reflected photon. In other words: the
Liberal claims that quantum theory is _level-1 indeterministic_. This leads to
the following conversation.

Conservative: “Of course, every good physical theory should tell us _what the
particles are going to do_ , and not just give us probabilities! Doesn’t this
just mean that you don’t know exactly all the details of your mirror? That you
just have to look at it more closely, and then you can actually predict
whether the photon will be reflected or transmitted?”

Liberal: “No. If my theory is correct, then it is in principle impossible to
predict this — the process is _intrinsically random_. In other words, I claim
that _nature simply does not carry enough structure_ to determine the outcome
of the experiment. This should not come as a surprise: for example, you have
already learnt from relativity that the notion of _simultaneity_ is,
surprisingly, not part of the furniture of the world, even though it
intuitively should be. I claim that quantum theory tells us that
_determination of measurement results_ is yet another piece of furniture that
has to go.”

Conservative: “But _what exactly_ is the content of the claim that the
transmission probability is $50\%$? When I repeat the experiment ten times,
does this tell me that the photon will be transmitted five times? You
explained to me that it does not. It could be six times, or actually all ten
times. Nothing is excluded and nothing predicted.”

Liberal: “Well, if you repeat the experiment many times (say, $n$ times), then
the law of large numbers tells you that there is a high probability that the
fraction of times $m$ it was transmitted (that is, $m/n$) is
$\varepsilon$-close to $1/2$.”

Conservative: “… there is a _high probability_ of that happening… You just
explained the meaning of $50\%$ probability to me by resorting to yet another
mention of probability. This is circular reasoning! I’m still waiting for your
explanation of what a probabilistic claim actually means.”

Liberal: “Yes, this reasoning is circular — the notion of probability _cannot_
ultimately be grounded in any deterministic notion. Nevertheless,
probabilistic claims are not meaningless. They resemble structure of the world
— though weaker structure than determinism — that allows us to place
successful bets. We have learned by experience how to use probabilities to act
rationally in the face of indeterminism. This is an empirical fact that’s hard
to deny.”

Half convinced, the conservative leaves and downloads a copy of the Liberal’s
lecture notes. In the meantime, the Liberal meets yet another physicist (the
Gambler) who has just proposed Postulates 3.2. These postulates describe a
_level-2 indeterministic theory_ : that is, one in which there is not a
_single_ probability distribution, but an _infinite set_ of possible
distributions that are supposed to describe the chances. The Liberal is
shocked.

Liberal: “Of course, every good physical theory should tell us _what the
probabilities are_ , and not just give us an infinite set of priors! Doesn’t
this just mean that you don’t yet know what the correct distribution is? I
guess you have to work a bit harder, until you can improve the postulates to
tell us the actual values of the probabilities!”

Gambler: “No. If my theory is correct, then it is in principle impossible to
say this — _nature simply does not carry enough structure_ to determine the
actual numerical values of probabilities. You must be well aware that we had
to let go of other beloved furniture of the world before.”

Liberal: “But _what exactly_ is the content of the claim that observer states
are described by the infinite set of algorithmic priors ${\mathbf{P}}_{U}$?
Does this mean that when I pick my favorite universal machine $U$, my future
states will be distributed according to ${\mathbf{P}}_{U}$? You explained to
me that it does not.”

Gambler: “Well, it tells you that if there is a computable regularity that you
have observed often enough, then for every ${\mathbf{P}}_{U}$ there will
ultimately be a high probability that this regularity remains. This is the
nature of algorithmic probability, or universal induction.”

Liberal: “… for _every ${\mathbf{P}}_{U}$ it will ultimately…_ But for some
${\mathbf{P}}_{U}$ it will happen faster than for others. So, suppose I have
seen a regularity $n$ times, then what is _the actual_ probability that this
regularity will remain? I’m still waiting for your concrete explanation of
what the set of ${\mathbf{P}}_{U}$ is supposed to mean.”

Gambler: “The notion of level-2 indeterminism cannot ultimately be grounded in
any level-1 notion. Nevertheless, level-2 claims are not meaningless. They
resemble structure of the world — though weaker structure than level-1 — that
allows us to place rational bets. In fact, I claim that this is _how we
actually bet in this world anyway_ : we can start with an arbitrary prior, and
use new data to update it. When you say that there is a $50\%$ chance that a
photon will be reflected or transmitted, you are basing this claim on a strong
belief that this is _really a half-silvered mirror_ , and that repetitions of
the experiment can be treated as exchangeable. But these are _also_ only
statements with certain probabilities attached to them (even if you think that
these probabilities are close to one), and so on, ad infinitum. The best a
physical theory can do is to tell us which _kinds of priors_ are admissible,
and which ones are not (for example, ones with a belief in the violation of
conservation laws).”

Convinced by some amount that is hard to quantify (perhaps half convinced,
perhaps $30\%$), the Liberal leaves… and starts to feel really old.

The position of the Gambler resembles some arguments that are also often heard
in another camp: by supporters of _QBism_ Fuchs ; FuchsSchack ; Timpson , i.e.
of (subjective) Quantum Bayesianism (or nowadays called “Quantum
Betabiliterianism” by its founders). QBists argue that the actual numerical
values of probabilities (or, for that matter, the concrete entries of a
quantum density matrix) are not themselves properties of the world, but
represent subjective beliefs. As the argument goes, it is instead _the update
rules (e.g. the Born rule) and the structure of the state space (e.g. the
Hilbert space dimension)_ that resemble actual “facts of the world”. In this
sense, QBists would perhaps agree that “quantum states represent beliefs which
are level-2”, whereas Postulates 3.2 should be understood as saying that
“objective chances are level-2”.

The idea of a _set_ of priors is not new. It has been studied in many
different forms under the name of _imprecise probability_ Walley , and it
appears in physics under the name of _equivalence of ensembles_ Lima1 ; Lima2
; MuellerAdlam . That is, in many situations, thermodynamics is understood as
a theory with predictions that agree for the canonical and microcanonical
ensembles, and it is in some sense arbitrary which ensemble to select.

There is another important advantage of postulating a set of priors over
picking a single distribution: it allows for a strong notion of _encoding
invariance_.

###  3.2 Encoding invariance

What do the bits in an observer state $x$ actually _mean_? Postulates 3.2
tells us that the length $\ell(x)$ says _how many_ state transition the
observer has suffered since its state of no information. Moreover, the order
of bits is relevant as well: if $x=x_{1}x_{2}\ldots x_{n}$, then the first bit
is the one that has been acquired first, the second bit came after this, and
so on.

But what about the meaning of “zero” versus “one”? Isn’t it naive to claim
that an observer’s first-person perspective is described by a bunch of bits in
the first place? This conceptual confusion can be clarified by taking a more
abstract point of view. According to this view, observer states themselves
_are_ not binary strings, but they can be _encoded_ into binary strings. Think
of an unspecified countably-infinite set $\mathcal{O}$ of observer states, and
a bijective map $\alpha:\mathcal{O}\to{\mathcal{S}}$ that tells us which
observer state is represented by which binary string. We assume that observer
states have additional structure: there is a distinguished _empty_ observer
state $o_{\varepsilon}$, and for every observer state $o$, there are _two_
different distinguished observer states $o^{\prime}$ and $o^{\prime\prime}$
that we can think of as “continuations” of $o$, encoding an additional answer
to some yes-no-question. Then $\alpha$ should be structure-preserving: it
should satisfy $\alpha(o_{\varepsilon})=\varepsilon$ and
$\ell(\alpha(o^{\prime}))=\ell(\alpha(o^{\prime\prime}))=\ell(\alpha(o))+1$.

Consider _another_ bijective structure-preserving encoding map
$\beta:\mathcal{O}\to{\mathcal{S}}$. The two maps $\alpha$ and $\beta$ encode
any $o\in\mathcal{O}$ into different binary strings, $x_{\alpha}:=\alpha(o)$
and $x_{\beta}:=\beta(o)$. Consequently,
$x_{\beta}=\beta\circ\alpha^{-1}(x_{\alpha})$. We can think of the bijective
map $\beta\circ\alpha^{-1}:{\mathcal{S}}\to{\mathcal{S}}$ as an _encoding
transformation_ : it preserves the length and prefix properties of any string,
but switches between two different possible encodings of observer states.

We need one additional piece of structure on the observer states: a
_computability structure_. Intuitively, we would like to say that both
$\alpha$ and $\beta$ should be computable. However, we have no idea what this
means. But whatever it _does_ mean, it should imply that the composition
$\beta\circ\alpha^{-1}$ is computable too — and, as a map on the binary
strings, computability of this function _is_ a well-defined notion. This
argumentation leads us to the following definition and theorem:

######  Theorem 3.3 (Encoding invariance).

Let $\varphi:{\mathcal{S}}\to{\mathcal{S}}$ be any _structure-preserving map_
on the observer states, i.e. a computable bijective map whose inverse is
computable, and which preserves prefixes in the sense that
$\varphi(\varepsilon)=\varepsilon$ and

$\varphi(\\{x0,x1\\})=\\{\varphi(x)0,\varphi(x)1\\}.$

Then the theory expressed by Postulates 3.2 is invariant under every such map;
that is,

$\\{{\mathbf{P}}_{U}\,\,|\,\,U\mbox{
universal}\\}=\\{{\mathbf{P}}_{U}\circ\varphi\,\,|\,\,U\mbox{ universal}\\},$

i.e. the set of algorithmic priors is invariant under structure-preserving
maps. As explained above, we can interpret this as a “freedom of choice of
encoding” of observer states into binary strings.

An example of a structure-preserving map is given by the _bitwise inversion_ :
for example, $\varphi(1011)=0100$. This theorem tells us that the predictions
of our theory do not change if we decide to switch zeros with ones in the
representation of observer states.

###### Proof.

Note that ${\mathbf{P}}_{U}\circ\varphi={\mathbf{P}}_{\varphi^{-1}\circ U}$,
i.e. the distribution ${\mathbf{P}}_{U}\circ\varphi$ can be obtained as the
one coming from a machine that works like $U$, but applies $\varphi^{-1}$ to
its outputs. Since $\varphi$ is structure-preserving if and only if
$\varphi^{-1}$ is, it only remains to show that

$\\{\varphi^{-1}\circ U\,\,|\,\,U\mbox{
universal}\\}\subseteq\\{U\,\,|\,\,U\mbox{ universal}\\}.$

In other words, we have to show that $V:=\varphi^{-1}\circ U$ is universal
whenever $U$ is universal. To see this, let $T$ be any monotone Turing
machine, hence $\varphi\circ T$ is a monotone Turing machine. Since $U$ is
universal, there is some $x\in{\mathcal{S}}$ such that $U(xp)=\varphi\circ
T(p)$ for all $p$, and so $V(xp)=\varphi^{-1}\circ U(xp)=T(p)$ for all $p$.
This proves that $V$ is universal. ∎

There is an intuitive analogy of these insights with differential geometry as
used, for example, in the theory of general relativity: the set $\mathcal{O}$
is analogous to the manifold of spacetime points, and the maps $\alpha$ and
$\beta$ correspond to two different coordinate systems. These coordinate
systems should preserve the differentiability structure of the manifold, and
the physical laws are invariant under changes of coordinates. Here, the
structure to be preserved is the observer states’ _computability structure_
(together with the prefix structure), and our theory is invariant under
changes of encoding.

Now that we have seen that a _set_ of priors is the way to proceed, we still
have to discuss why this set should be chosen as the set of _algorithmic_
priors. In Section 2, we have given an intuitive motivation for selecting
algorithmic probability: it is in some sense a “natural probability
structure”, derived from the structure of mathematics alone, without the need
for any further choices. The next subsection will give a second, independent
argument.

###  3.3 Why use algorithmic probability?

Our choice of algorithmic probability can also be understood in a pragmatic
way, namely as the result of extrapolating a successful method of prediction
to a larger and more general domain: Solomonoff induction Hutter ; LiVitanyi .

In a nutshell, Solomonoff induction is a simple prescription for predicting
future data, given previous data. Suppose that a random process generates one
bit $x_{1},x_{2},\ldots$ after the other, according to an unknown and perhaps
very complicated measure $\mu$. Think of a scientist who receives these bits,
and is supposed to predict _the probability of the next bit_ ,
$\mu(a|x_{1}\ldots x_{n})$. There is one extra promise that may help the
scientist to place her guess: that $\mu$ is _computable_. That is, there
exists a (potentially extremely inefficient) algorithm that, on input
$x=x_{1}\ldots x_{n}$ and $n\in\mathbb{N}$, outputs an $n$-digit approximation
of $\mu(x)$. Needless to say, neither $\mu$ nor this algorithm are known to
the scientist.

Solomonoff induction is the following prescription: _as a good guess for
$\mu(a|x)$, use algorithmic probability ${\mathbf{P}}(a|x)$_. That is all. As
we will study in more detail in Section 4.4, this guess ${\mathbf{P}}$ is
guaranteed to be close to the actual probability $\mu$ in the limit of
$n\to\infty$.

Solomonoff induction works in the context of computable, probabilistic
processes — and there is one particularly relevant process of this kind: _our
physical world_ , as it presents itself to the observations of a physicist.
Given data on initial conditions of some physical system, we can in principle
write a computer program that simulates the laws of physics as we know them
and produces predictions for all observations that we may perform on the
system at later times. While these predictions will in general be
probabilistic (as dictated by quantum theory), the statistical inferences that
we draw from them are in great agreement with our actual observations. It is a
remarkable empirical finding that the notion of “universal computation”, based
on the Turing machine Turing ; Cooper , seems to capture every kind of process
in our universe that can be subjected to this kind of controlled empirical
analysis666This is a statement of _principle_ and not of _practice_. For all
practical purposes, it may e.g. remain forever impossible to produce an
accurate simulate of the statistics of all of planet Earth in any detail (as
described by quantum theory or any future theory), even though the physical
Church-Turing thesis claims that a corresponding (extremely inefficient)
algorithm exists in principle..

This observation and its extrapolation to all physical experiments that we may
perform in the future — sometimes called the “physical version” of the Church-
Turing thesis777While the original Church-Turing thesis does not directly
relate to physics, several different versions of this thesis have been
formulated over the decades. The version that we refer to here resembles, for
example, Wolfram’s WolframBook  “principle of computational equivalence”. It
has been analyzed in more detail by Gandy Gandy , who calls (something very
similar to) it “Thesis M”, and in the quantum context by Arrighi and Dowek
Arrighi . For an overview and discussion of different versions of the Church-
Turing thesis, see e.g. Hofstadter ; PiccininiTuring . — is supported by
experience and a variety of arguments. All theoretical attempts to construct
reasonable mathematical models of computation, especially under the constraint
to be realizable in our physical world, have so far turned out to be
equivalent to the Turing machine model. This includes quantum computers, which
can compute exactly the same class of functions as classical ones (the fact
that they may be superpolynomially faster at some tasks Deutsch  does not
invalidate the formulation of the thesis that we are considering here since we
may ignore questions of efficiency). Despite some claims in the opposite, no
physical system performing “hypercomputation” has ever been identified Davis .

This implies a very simple and at the same time surprising consequence:
_Solomonoff induction can be used to make successful predictions in our
physical world_ — predictions that must agree with those of our best physical
theories (or even better future theories) if their regime of applicability is
the regime of data collection. Solomonoff induction will automatically
“discover” the probabilistic laws of nature that we already have (such as
quantum theory), or possible future ones. In some sense, Solomonoff induction
can thus be seen as a formal analogue of the scientific method itself.

One of the major motivations of this paper is the insight that there are
regimes of experience that we are currently entering which go beyond the
standard domain of physics, cf. Table 1: for example, we are interested in the
experience of observers in extremely large universes (cosmology and the
Boltzmann brain problem), or we would like to understand what an agent is
going to see if her brain is simulated on a computer (philosophy of mind). The
problem is that physics as we currently know it is not designed to address
these questions, at least not directly, as heralded by the controversial
discussions that characterize these fields. It is at this point where the
insight above is quite suggestive: _Solomonoff induction agrees perfectly with
our best physical theories in the usual regime of physics, but it can also be
applied in more exotic domains_. But then, there is an obvious approach that
we can take: _Go ahead and apply Solomonoff induction to these new regimes of
experience!_

Applying Solomonoff induction means nothing but predicting the future
according to conditional algorithmic probability. But this is exactly what
Postulates 3.2 are claiming: namely, that the chances of our future
observations are given by conditional algorithmic probability. In this sense,
our postulates can be seen as simply formalizing the prescription that we have
derived above — namely, to apply Solomonoff induction in _all_ situations in
which we may ask “what will I see next?”888In more detail, the prescription is
not to _actually use Solomonoff induction to predict the future_ , because we
cannot know all details of our observer states (and we cannot compute
algorithmic probability). It is rather the idea that we should _think of
algorithmic probability as dictating what happens in these new regimes of
experience_ , and then do our best to extract concrete predictions from this
claim..

In the rest of the paper, we are indeed going to do exactly that. For example,
we will apply Solomonoff induction to exorcise Boltzmann brains in Subsection
6.1, and we will derive predictions on the computer simulation of agents in
Subsection 6.2. By doing so, we will work with Postulates 3.2, but will
sometimes speculate what would happen if we instead had a better theory that
realizes Postulates 3.1.

The description above may render Solomonoff induction almost “magical”,
showing that it is somehow automatically consistent with our best physical
theories. But all that the above really says, at least up to this point, is
that _agents who have made observations in agreement with our physical
theories in the past should bet on the validity of those theories in the
future_. This is simply a manifestation of universal induction. Clearly, our
theory should say more than that to be considered successful: it should
explain _why_ these past observations, indicating the presence of simple
computable laws within an external world with certain properties, are to be
expected in the first place. This is what we are going to address next.

##  4 Emergence of an external physical world

_“The only thing harder to understand than a law of statistical origin would
be a law that is not of statistical origin, for then there would be no way for
it […] to come into being. On the other hand, when we view each of the laws of
physics […] as at bottom statistical in character, then we are at last able to
forego the idea of a law that endures from everlasting to everlasting.”_ (John
A. Wheeler, “Law Without Law” Wheeler ).

Now we are ready to prove the first consequence of our postulates: that
observers will, with high probability, see an external world that is governed
by _simple, computable, probabilistic_ laws (that is, laws that assign
probabilities to observations and which have a short description), but the
form of these laws will itself be contingent. Before showing this in full
generality, let us start with a first “warm-up” that gives us some intuition
as to why and how regularities may emerge and stabilize themselves.

###  4.1 Warm-up: persistence of regularities

Suppose that an observer is currently in observer state $x$. Then, her state
will subsequently change to a longer strong $xy$, with probability

${\mathbf{P}}(y|x)\geq\mathbf{M}(y|x)=\frac{\mathbf{M}(xy)}{\mathbf{M}(x)}\geq\frac{2^{-{\rm
Km}(xy)}}{\mathbf{M}(x)}.$

This inequality tells us that transitions to those $xy$ tend to be preferred
which are “more natural continuations” of the previous state $x$. That is, if
$xy$ has a short description, i.e. if ${\rm Km}(xy)$ is small, then the
corresponding $xy$ tends to occur with higher probability than other possible
states $xy^{\prime}$. Thus, simplicity in the sense of compressibility is
favored. Intuitively, highly compressible histories (or strings) are those
that contain _regularities_ which can be used to generate shorter
descriptions.

How can we define the notion of “regularities” and prove that they are somehow
favored by algorithmic probability ${\mathbf{P}}$? It turns out that an
abstract approach is the most simple and powerful one: namely, defining a
“regularity” of an observer state $x$ as some property for which a computer
program can check in finite time whether or not it is present:

######  Definition 4.1 (Computable tests).

A computable function $f:{\mathcal{S}}\to\\{0,1\\}$ is called a _computable
test_. A computable test is called _sustainable_ if $f(\varepsilon)=1$ and if
for all $x\in{\mathcal{S}}$ with $f(x)=1$ there is some bit $a\in\\{0,1\\}$
with $f(xa)=1$.

In a nutshell, a computable test is sustainable if whenever it gives the
answer “yes”, it can possibly still give the answer “yes” in the next moment.

Imagine an observer in state $x=x_{1}x_{2}\ldots x_{n}$ (where the $x_{i}$ are
the bits), and suppose that there is a computable test $f$ such that
$f(x_{1})=f(x_{1}x_{2})=\ldots=f(x_{1}\ldots x_{n})=1$. This describes a
regularity: all previous observer states (including, for example,
observations) had the property that the test $f$ yielded the outcome “yes”. In
this case, the observer may be led to believe that $f$ will yield “yes” in the
next moment, too. The following theorem, inspired by HutterConfirmation ,
shows that this guess will asymptotically be correct due to the properties of
algorithmic probability. We use the notation $x_{1}^{k}:=x_{1}x_{2}\ldots
x_{k}$ if $x=x_{1}\ldots x_{n}$ and $k\leq n$.

######  Theorem 4.2 (Persistence of regularities).

Let $f$ be a sustainable computable test. For bits
$a_{1},\ldots,a_{n},b\in\\{0,1\\}$, define the measure $p$ as

$\displaystyle p(b|a_{1}a_{2}\ldots
a_{n}):={\mathbf{P}}\\{f(x_{1}^{n+1})=b\,\,$ $\displaystyle|$
$\displaystyle\,\,f(x_{1}^{1})=a_{1},\ldots,$ $\displaystyle
f(x_{1}^{n})=a_{n}\\}.$

Then we have $p(1|1^{n})\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}1$, and the convergence is rapid since
$\sum_{n=0}^{\infty}p(0|1^{n})<\infty$. That is, _computable regularities that
were holding in the past tend to persist in the future_.

###### Proof.

Since $f$ is a sustainable computable test, there is an algorithm that
constructs an infinite string $z\in\\{0,1\\}^{\infty}$ with the property that
$f(z_{1}^{k})=1$ for all $k\in\mathbb{N}$. Namely, the algorithm starts with
the empty string, and then picks some bit $z_{1}$ such that $f(z_{1})=1$, and
then picks some next bit $z_{2}$ such that $f(z_{1}z_{2})=1$, and so forth.
Define

$p(a_{1}a_{2}\ldots
a_{n}):=\sum_{x\in\\{0,1\\}^{n}:f(x_{1})=a_{1},\ldots,f(x_{n})=a_{n}}{\mathbf{P}}(x),$

which yields a measure in the sense of Definition 2.2. Its conditional version
$p(b|a)$ is the quantity we are interested in. Let $\mu$ be the computable
measure with $\mu(x)=1$ if $x$ is a prefix of $z$, and $0$ otherwise. Since
$\mathbf{M}$ is a universal enumerable semimeasure, there is some constant
$c>0$ such that $\mathbf{M}(x)\geq c\,\mu(x)$ for all $x\in{\mathcal{S}}$,
thus

$p(1^{n})\geq{\mathbf{P}}(z_{1}^{n})\geq\mathbf{M}(z_{1}^{n})\geq
c\,\mu(z_{1}^{n})=c\quad\mbox{for all }n\in{\mathbb{N}}.$

On the other hand, $p(1^{n})=\prod_{j=0}^{n-1}p(1|1^{j})$, hence

$\log c\leq\sum_{j=0}^{n-1}\log
p(1|1^{j})\leq\sum_{j=0}^{n-1}\left(p(1|1^{j})-1\right).$

Since this is true for all $n$, the claim follows. ∎

As a simple example, consider the “frequency of ones” of some string $x$,
defined as $\\#_{1}(x)/\ell(x)$, where $\\#_{1}(x)$ is the number of ones in
$x$ (for example, $\\#_{1}(1011)=3$). Let us define a computable test $f$ that
asks whether the frequency of ones is larger than $90\%$. This is only an
interesting question for longer strings. For all $x\in{\mathcal{S}}$ with
$\ell(x)\geq 10$, set

$f(x):=\left\\{\begin{array}[]{cl}1&\mbox{if }\\#_{1}(x)/\ell(x)\geq 0.9\\\
0&\mbox{otherwise}.\end{array}\right.$

and for strings $x\in{\mathcal{S}}$ with $\ell(x)\leq 9$, set $f(x):=1$ if and
only if $x$ is a prefix of any string $y$ of length $10$ with $f(y)=1$. For
example, $f(1101111111)=1$, hence $f(110)=1$ and $f(\varepsilon)=1$.

This is a computable test, but is it sustainable? Suppose that $f(x)=1$ and
$\ell(x)\leq 9$, then there exists some $a\in\\{0,1\\}$ with $f(xa)=1$ by
construction. If $\ell(x)\geq 10$, the

$\frac{\\#_{1}(x1)}{\ell(x1)}=\frac{\\#_{1}(x)+1}{\ell(x)+1}\geq\frac{\\#_{1}(x)}{\ell(x)}\geq
0.9,$

hence $f$ is indeed sustainable. Thus, Theorem 4.2 that _an observer that has
been in states with more than $90\%$ of ones for long enough will probably
continue to be in states with this property in the future_.

However, a moment’s thought shows that Theorem 4.2 doesn’t really say very
much: facts can change, and the answers to yes-no-questions can flip over
time. This simple observation creates a puzzle of relevance far beyond this
paper, which is known under the name of “Goodman’s new riddle of induction”
Goodman . To illustrate this, consider another sustainable computable test $f$
which simply asks whether the observer state’s last bit equals one. Fix some
very large number $N\in{\mathbb{N}}$ (say, one with large Kolmogorov
complexity ${\rm K}(N)\gg 1$), and define a modified test $f^{\prime}$ by

$f^{\prime}(x):=\left\\{\begin{array}[]{cl}f(x)&\mbox{if }\ell(x)\leq N,\\\
1-f(x)&\mbox{if }\ell(x)>N.\end{array}\right.$

The computable test $f$ seems as simple or “natural” as properties like
“green” or “blue”, whereas $f^{\prime}$ resembles Goodman’s properties “grue”
or “bleen”: _“Is the observer young and her last bit equals one, or is she old
and her last bit equals zero?”_ Now if our observer has seen that
$f(x_{1})=\ldots=f(x_{1}x_{2}\ldots x_{n})=1$, but $n\leq N$, then Theorem 4.2
applies to both $f$ and $f^{\prime}$. So what should the observer bet on —
that the last bit switches at some point?

This puzzle is resolved by noting that Theorem 4.2 gives only an asymptotic
statement: it only says that _if $n$ is large enough_, then $f$ (resp.
$f^{\prime}$) will yield the answer “yes“ (i.e. $1$) with high probability in
the future, if it did in the past. Intuitively, what happens is that the
regularity $f=1$ stabilizes itself much faster than the regularity
$f^{\prime}=1$. In particular, if $n=N$, then we expect that
$f(x_{1}x_{2}\ldots x_{n+1})=1$ has higher probability than
$f^{\prime}(x_{1}x_{2}\ldots x_{n+1})=1$, since $f$ is a _simpler_ computable
test, and thus the corresponding regularity statement is preferred by
algorithmic probability. Intuitively, the regularity $f^{\prime}$ would
stabilize itself only after $n\gg N$ and if the observer has _in fact_ seen
her last bit switch. In the notation of the proof of Theorem 4.2, we have

$-\log c=\mathrm{K}(\mu)+\mathcal{O}(1)\leq\mathrm{K}(f)+\mathcal{O}(1),$

which means that $\sum_{n=0}^{\infty}p(0|1^{n})$ (a measure of the “total
exceptions from the rule”) tends to be smaller if $f$ has a shorter
description length.

This simple example teaches us two things. First, we should not only look at
regularities, but also at their _complexities_ — simple regularities will be
more relevant. Second, instead of answering a single yes-no-question, we
should try to answer a multitude of questions as parts of some “web of
knowledge”. We would like to show that the regularities fit together to give
the observer a coherent notion of a “world”. This is what we are going to
address next.

###  4.2 Computable laws and the external process

Having studied a (rather weak) notion of “persistence of regularities” in the
previous subsection, it is clear that physics as we know it has much more to
offer. For example, regularities in physics are often at the level of the
_statistics_ rather than in the actual results. In particular in the context
of quantum theory, when we talk about “simple laws of physics”, we have
simplicity in a peculiar form: the _probabilistic laws themselves_ seem to be
simple, but the _individual measurement outcomes_ turn out to be complex.

As an example999This is a rather naive example to illustrate the main idea,
not a profound statement about the foundations of quantum mechanics. To study
the exact nature of randomness in quantum mechanics, one would have to dive
into the subject of interpretations, and also into the field of device-
independent randomness amplification ColbeckThesis ., consider a single
quantum spin-$\frac{1}{2}$-particle (a qubit) and the following experimental
setup: the spin is first measured in $Z$-direction, then in $X$-direction,
then in $Z$-direction again and so on — that is, $Z$\- and $X$-directions are
alternately measured on the single qubit; in total, there are $n$
measurements. Assume for the sake of the argument that the particle starts in
a quantum state where the spin points exactly in $X$-direction. Whenever the
result is “spin-up”, it will be denoted by a one, and “spin-down” will be
denoted by a zero. The result of the measurement is a binary string,
consisting of $n$ bits which encode the measurement outcomes.

Denote the eigenstates in $Z$-direction by $|0\rangle$ and $|1\rangle$, and
those in $X$-direction by $|+\rangle=(|0\rangle+|1\rangle)/\sqrt{2}$ and
$|-\rangle=(|0\rangle-|1\rangle)/\sqrt{2}$. The particle starts in state
$|+\rangle$. Thus, the first measurement (which is in $Z$-direction) will
yield outcome “spin-up” or “spin-down” with probability $\frac{1}{2}$ each.
After that measurement, by the projection postulate, the state of the system
will be either $|0\rangle$ or $|1\rangle$. But then, the following measurement
in $X$-direction will again yield spin up or down with probability
$\frac{1}{2}$ each, and so on. According to elementary quantum mechanics, the
resulting string will be completely random (and there are good arguments that
this randomness is irreducible and not just “apparent” in some sense
ColbeckThesis ; Pironio ).

In the end, the situation is equivalent to $n$ tosses of a fair coin: the $n$
bit values are independently and identically distributed. But a string
$x\in{\mathcal{S}}$ that is generated by such a process is incompressible with
high probability ZvonkinLevin ; Brudno , i.e. its monotone complexity ${\rm
Km}$ is close to maximal, such that ${\rm Km}(x)\approx n=\ell(x)$.

In this example, the rules of quantum mechanics (which yield the outcome
probabilities) are very simple, but the outcomes themselves are arbitrarily
complex. This is a typical situation in physics. In what follows we will show
that this kind of behavior is predicted by the theory of this paper.

Our main technical tool will be the formulation of Solomonoff induction
LiVitanyi ; Hutter  as the following theorem (LiVitanyi, , Corollary 5.2.1).
It rests on a slightly different interpretation of _measures_ $\mu$ as defined
in Definition 2.2: namely, as probability measures in the set of infinite
strings $\\{0,1\\}^{\infty}$. The idea is that a statement like
$\mu(101)=\frac{1}{4}$ should be understood as saying that the _set of all
infinite strings that start with $101$_ has measure $\frac{1}{4}$. Such sets
are called _cylinder sets_ and denote, as in this example, $[101]$. Then, as
subsets of $\\{0,1\\}^{\infty}$, we have for example the disjoint union
$[10]=[100]\cup[101]$, and consequently $\mu(10)=\mu(100)+\mu(101)$. Formally,
the cylinder sets generate a $\sigma$-algebra on $\\{0,1\\}^{\infty}$ on which
$\mu$ is a probability measure. The measure-theoretic details can be found in
LiVitanyi .

######  Lemma 4.3 (Solomonoff induction).

Let $\mu$ be a computable measure. Then there is a set
$S\subseteq\\{0,1\\}^{\infty}$ of $\mu$-measure one, such that for every $x\in
S$ and every $b\in\\{0,1\\}$

$\mathbf{M}(b|x_{1}^{n})\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}\mu(b|x_{1}^{n}).$

Moreover, for all $x\in S$, we have asymptotic normalization:

$\sum_{b\in\\{0,1\\}}\mathbf{M}(b|x_{1}^{n})\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}1.$

The arrow is to indicate that the difference between left- and right-hand side
turns to zero, not that both sides converge individually. In this equation,
$x=x_{1}x_{2}x_{3}\ldots$ is an infinite binary string, and
$x_{1}^{n}=x_{1}x_{2}\ldots x_{n}$ denotes the string of length $n$ that
consists of the first $n$ bits of $x$.

What does this mean? Consider a physicist who observes a certain random
process which emits random bits $x_{1},x_{2},\ldots$. Suppose that the
physicist has no idea what random process it is; all she knows is that there
is _some_ underlying probability measure $\mu$ that describes the process
accurately, and that $\mu$ is computable. Despite her ignorance, she would
like to predict the probability of future outcome bits.

This situation is in principle close to what scientists are doing when they
try to uncover the hidden mechanisms of nature; it is a simple model of
science. The lemma above now says that in the long run, i.e. for large $n$,
the physicist may simply use the universal semimeasure $\mathbf{M}$ (or,
equivalently, the measure ${\mathbf{P}}$) to predict the probability of the
next outcomes. This is Solomonoff induction: algorithmic probability is used
as a tool for prediction.

A simple example is given in HutterConfirmation ; LiVitanyi : suppose that the
unknown process is actually deterministic and emits only $1$’s, that is,
$\mu(1^{n})=1$ for all $n\in{\mathbb{N}}$, where $1^{n}=111\ldots 1$ is the
string of length $n$ consisting only of $1$’s. Then the probability that
Solomonoff induction predicts a $0$ as the next bit is asymptotically
$\mathbf{M}(0|1^{n})=2^{-{\rm K}(n)+\mathcal{O}(1)}$, which is of the order
$1/n$ for most $n$. In particular, this converges to the “correct” probability
zero for large $n$.

This formulation of Solomonoff induction will have several applications in the
following. As our first application, we will see that it can give us a
surprising prediction: that our theory implies the emergence of an external
world in some sense. Let us first state the theorem, and then discuss its
interpretation.

######  Theorem 4.4 (Asymptotic computability).

Let $\mu$ be some computable measure. Then,

${\mathbf{P}}\left\\{{\mathbf{P}}(b|x_{1}\ldots x_{n})\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}\mu(b|x_{1}\ldots x_{n})\,\forall
b\right\\}\geq 2^{-{\rm K}(\mu)};$

that is, with probability at least $2^{-{\rm K}(\mu)}$ (which is large if and
only if $\mu$ is simple), the actual transition probability ${\mathbf{P}}$
will in the long run converge1010footnotemark: 10 to the computable measure
$\mu$.

99footnotetext: Regarding the speed of convergence, it seems to be a generic
phenomenon that the standard notion of limit (for every $\delta>0$ there is
some $N\in\mathbb{N}$ such that the difference is smaller than $\delta$ for
all $n\geq N$) does not yield the strongest or most relevant notion of
convergence in this context. That is, one would expect that even for “most”
$n<N$, the difference is small already. This is a consequence of the irregular
behavior of Kolmogorov complexity, and can be seen nicely in the example on
page 4.2: we have $\mathbf{M}(0|1^{n})=2^{-{\rm K}(n)+\mathcal{O}(1)}$. This
expression tends to zero, but does so extremely slowly, since there are always
astronomically large $n$ with exceptionally small complexity ${\rm K}(n)$.
However, it is close to zero (or, in more detail, to $1/n$) for _most_ $n$,
since most $n$ have ${\rm K}(n)\approx\log n$. An observer subject to a random
process with transition probabilities $\mathbf{M}(b|1^{n})$ (or of some other
sort where outcomes actually vary) will thus typically not notice the
exceptional values of $n$, and see convergence much faster than in the formal
$\delta$-criterion. This shows that Theorem 4.4 features a perhaps too strong
form of convergence, and it might be more relevant to ask whether
$\mu$-typicality of outcomes might be a “persistent regularity” (in the sense
of Theorem 4.2), for example.

That is, in the long run, it happens with probability at least
$2^{-\mathrm{K}(\mu)}$ that algorithmic probability converges to the
computable measure $\mu$. This probability is larger for _simpler_ $\mu$, i.e.
for ones that have small Kolmogorov complexity $\mathrm{K}(\mu)$ as defined in
Definition 2.5.

###### Proof.

Since ${\mathbf{P}}$ is just a normalized version of $\mathbf{M}$, Lemma 4.3
and asymptotic normalization imply that there is a Borel set
$S\subseteq{\mathcal{S}}^{\infty}$ with $\mu(S)=1$ such that
$\mathbf{M}(b|x_{1}^{n})-\mu(b|x_{1}^{n})\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}0$ for all $x\in S$. On the other hand, let
$\varepsilon_{n}(x):=1-\sum_{b\in\\{0,1\\}}\mathbf{M}(b|x_{1}^{n})$, then the
same lemma shows that $\varepsilon_{n}(x)\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}0$ for all $x\in S$, and

$\mathbf{M}(b|x_{1}^{n})\leq{\mathbf{P}}(b|x_{1}^{n})=\frac{\mathbf{M}(b|x_{1}^{n})}{1-\varepsilon_{n}(x)},$

and so ${\mathbf{P}}(b|x_{1}^{n})-\mu(b|x_{1}^{n})\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}0$ for all $x\in S$. But for every finite
string $x\in{\mathcal{S}}$, Theorem 2.5 shows that
${\mathbf{P}}(x)\geq\mathbf{M}(x)\geq 2^{-{\rm K}(\mu)}\mu(x)$. According to
elementary measure theory, this inequality must then also be true for $S$,
i.e. ${\mathbf{P}}(S)\geq 2^{-{\rm K}(\mu)}\mu(S)$, lower-bounding the
probability of the stated event as claimed101010It is tempting to conjecture
an alternative proof of Theorem 4.4 in the following way. Let
$p\in{\mathcal{S}}$ be a minimal program for $\mu$ in the sense of Theorem
2.5; in particular, $\ell(p)={\rm K}(\mu)$. Consider the set of infinite
strings $T:=\\{pq\,\,|\,\,q\in\\{0,1\\}^{\infty},\enspace q\mbox{ is
Martin-L\"{o}f random}\\}$, and the corresponding set $S$ of infinite output
strings that are generated by our universal reference machine $U$ if all
strings of $T$ are chosen as inputs. Since almost all infinite strings are
Martin-Löf random, we have $\mu(S)\geq 2^{-\ell(p)}=2^{-{\rm K}(\mu)}$, and
these output strings should be “$\mu$-typical” since the strings in $T$ are,
and thus satisfy the property stated in Theorem 4.4. However, Exercise 5.2.8
in LiVitanyi  shows that the latter assertion is not quite true. Thus, one
needs more refined arguments to make this proof idea work. See also the result
of HutterMuchnik . . ∎

While I do not know whether the the event in Theorem 4.4 (i.e. convergence to
_some_ computable measure $\mu$) happens with total probability one, we can
interpret it in a way that suggests that some possibly weaker form should
always be true. Namely, it seems to say that all regularities which persist
according to Theorem 4.2 will tend to “fit together” into a coherent overall
lawlike behavior. That is, if the answers to several computable tests $f$ all
remain “yes”, then this can be interpreted as consequences of a single
computable statistical law (namely $\mu$) which yields $\mu$-typical outcomes.
Since $\mu$-typicality of the sequence of observations is a much weaker
statement than the convergence of probabilities in Theorem 4.4, it might still
hold in all cases even if that strong convergence does not happen with unit
probability. We leave a more detailed analysis of this to future work.

In the following, we will assume that the event of Theorem 4.4 happens, for
some $\mu$. This assumption is also natural in the context of the “desired”
(not yet realized) Postulates 3.1: if we have a theory that admits processes
of “forgetting”, then the event of Theorem 4.4 describes a situation in which
an observer accumulates more and more information, and fully remembers all its
earlier state. Now, the idea is that as long as this process continues, there
is a tendency for regularities to stabilize, and for a resulting computable
measure $\mu$ to determine the asymptotic transitions. However, if the
observer loses most of her memory, then the process will basically restart,
and there is yet another chance for asymptotic computability described by some
measure $\mu$. If this repeats often enough, then the event of Theorem 4.4
will eventually happen.

We will now argue that Theorem 4.4 predicts that observers should expect to
see two facts which are features of physics as we know it: first, the fact
that there is an _simple, computable, probabilistic external world that
evolves in time_ (a “universe”), and second, that this external world seems to
have had an absolute beginning in the past (the “Big Bang”).

Let us start by taking these two features as empirically confirmed facts about
our physical world, and look at the “informational” consequences of these
facts in the context of algorithmic complexity. A possible analysis (assuming
a certain view on the quantum state that we do not need to share) has been
performed by Tegmark Tegmark  in a paper with the title _“Does the universe in
fact contain almost no information?_

In this paper, Tegmark argues that the universe’s quantum state at (or shortly
after) the Big Bang has been very simple, in the sense that it had in
principle a very short description. Furthermore, there seem to be
algorithmically simple laws of nature determining the state’s time evolution.
Thus, there should in principle exist a concise complete description of the
current quantum state of the universe: simply append a description of the
physical laws and a description (in some coordinate system) of the time that
has passed since the Big Bang to a description of this initial quantum state.
From this, a computationally immensely complex but algorithmically very simple
computer program will be able to extract the present quantum state of the
universe.

If we continue to accept Tegmark’s Everettian view of quantum mechanics for
the sake of the argument, then we can argue as follows. If, instead of the
full quantum state, we restrict our attention to _observations in typical
branches of the wavefunction_ , then these observations will nevertheless look
very complex, i.e. have large Kolmogorov complexity. The reason is very
similar to, say a classical coin tossing process. While the process itself has
a very short description, the actual sequence of outcomes of, say, $10^{9}$
coin tosses will typically have very high Kolmogorov complexity (namely, about
$10^{9}$).

We can thus reformulate the two empirical facts about our universe in
informational terms: observers make observations that are typically complex,
but that are nevertheless described by an algorithmically simple evolution of
an external world. This external world has the property that its evolution
will in general only allow _probabilistic_ predictions of future observations.

Let us now see how these observations can be understood as consequences of
Theorem 4.4. If the event that is described in this theorem happens, then the
transition probability ${\mathbf{P}}$ will converge to a simple computable
measure $\mu$,

${\mathbf{P}}(b|x_{1}\ldots x_{n})\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}\mu(b|x_{1}\ldots x_{n}),$

where ${\rm K}(\mu)$ is likely small. According to the definition in Theorem
2.5 this means the following. Denote the universal reference machine by $U$.
Then there is a short computer program (a finite binary string) $q$ of length
$\ell(q)={\rm K}(\mu)$ with the property that

$\sum_{p:U(qp)=x*}2^{-\ell(p)}=\mu(x)$ (5)

for all finite strings $x\in{\mathcal{S}}$. That is, the computer program $q$
causes the universal machine $U$ to operate in the following manner:

  * •

after having read the prefix $q$ from its input, the monotone Turing machine
enters a particular mode of computation. In this mode, it sequentially reads
further (random) bits from the input tape (the finite sequence of these bits
that have previously been read, at any given time step, is called $p$).

  * •

The machine does (possibly very complex) computations in its working memory,
and

  * •

sometimes produces a new output $x_{i}$ on its output tape, building up an
output string $x_{1}x_{2}x_{3}\ldots$.

Attaching the weights $2^{-\ell(p)}$ to the input strings $p$ can be
interpreted as supplying independent, identically distributed random bits to
the machine $U$ as input. These bits are read by the machine, and processed in
a computation which produces outputs from time to time. The outputs are
distributed according to $\mu$. The sequence of output bits
$x_{1}x_{2}x_{3},\ldots$ constitutes the observer’s (say, Alice’s) sequence of
observer states, with $x_{1}^{n}=x_{1}\ldots x_{n}$ her current state. If
Alice herself — or an imaginary bystander — would like to predict her next
state, then there are now two possibilities: first, predict
${\mathbf{P}}(b|x_{1}\ldots x_{n})$ directly. But this is certainly hard,
given that algorithmic probability is not computable. Second, predict
$\mu(b|x_{1}\ldots x_{n})$ — which is the probability that the machine $U$
will generate $b$ as its next output bit, in the course of the process that we
have just described.

But this allows a much more natural way of prediction: _given all you know (as
encoded in $x_{1}^{n}$), make a model of the state of the machine $U$ and of
its inner workings. Then, use _that_ for prediction._ Given that the machine
implements a _computable stochastic process_ , unfolding according to a simple
algorithm of short description, this promises to be a much more plausible
endeavor.

Figure 2: As explained in the main text, we can abstract from the concrete
monotone Turing machine model. It is irrelevant that we have used a colorful
model with tapes, internal memory etc. in our definition; all that counts is
the resulting abstract notion of computational process. An observer’s sequence
of states corresponds to the outputs of a machine that generates the
asymptotic measure $\mu$. We can obtain the observer’s state by simply reading
off the output from the output tape, which defines a function $f_{A}$ as
sketched on the left-hand side. In the picture of the abstract computational
process, this corresponds to a computable random variable $f_{A}$ that reads
off the output (that is, the current state) from wherever it appears in that
process, with $g(t)$ the complete state of this process at computational time
$t$. This is the formulation that we will use later in this paper. An observer
will regard this computational process as her “external world”, and $f_{A}$
can be interpreted as a “locator function”.

Indeed, it is arguably what _human observers_ do to predict: given the data
that we hold (some of which is collected by our senses), we infer properties
of a hypothetical process (the external world) that is not directly “part of
us”, but that turns out to be correlated to our future observations.
(“According to the signals that my eyes have just sent me, there seems to be a
tiger approaching… I better run…”)

The situation for Alice is similar: her changes of observer state (her
“experience”) is shaped by the fact that she is only a small part of a
“bigger” process, namely the computational process that would be run if the
universal machine $U$ was to produce $\mu$ via the shortest program. If Alice
is smart enough, she may actually discover this, and call this computational
process her “external world”. This process will have some simple structure
since it is governed by a short computer program.

One should not think too naively about this computation: this insight does
_not_ suggest that Alice should see actual tapes, binary digital memory or
other specific aspects of a monotone Turing machine’s hardware in her external
world. A computation in the mathematical sense should be regarded as a process
that is abstracted from the underlying machine model. While we have defined
the algorithmic priors ${\mathbf{P}}_{U}$ (and the corresponding
$\mathbf{M}_{U}$) in terms of universal monotone Turing machines, these
measures can also be characterized in abstract ways that do _not_ refer to
such machines — for example as _(universal) enumerable semimeasures_ similarly
to Theorem 2.5.

This demonstrates that we would obtain the same theory (and set of measures)
if we started with a very different machine model — say, a model where
computation is not carried out on tapes, but in a way which more closely
resembles a cellular automaton. The choice of model of computation is
arbitrary and can be exotic, as long as it can in principle be simulated by a
monotone Turing machine, and (in the universal case) is in principle able to
simulate every monotone Turing machine111111In particular, there is no need to
postulate that input bits are distributed independently identically at random,
as (5) seems to suggest at first sight Sterkenburg .. All we need is a notion
of sequentiality in reading the input (in order to define a semimeasure
$\mathbf{M}$ in the first place), and a distinguished way to “read off” the
machine’s output during the computation; all else can simply be regarded as an
abstract computational process. This is explained in more detail in Figure 2,
which also shows how we will use these abstract notions later in this paper.

While Alice should not expect to see binary digits or output tapes directly in
her external world, there are some properties that are common to _all_
computational processes. One of them is the fact that computations initially
start in a simple state (at least if the computer program has small
algorithmic complexity, which is the case here), and tend to become more and
more complex during the computation. This complexity comes from the unfolding
of logical depth and computational complexity over many time steps, and in our
case also from the random input bits.

Since the computer program has small algorithmic complexity, the computation
itself will correspond to a simple algorithm. In principle, Alice may be able
to determine a description of this algorithm or of some of its properties, and
predict future time evolution according to these “laws of nature”. Likewise,
Alice can use her knowledge of these laws to “calculate backwards”, and to
retrodict the process’ past states, given her knowledge about its current
state. This may include internal process times that have been before the
machine has produced any output; in this sense, before what she might be
tempted to call her “birth”.

If she continues extrapolating backwards to retrodict earlier and earlier
states of her universe, she will typically find simpler and more “compact”
states, with measures of entropy or algorithmic complexity decreasing — simply
because she is looking at earlier and earlier stages of an unfolding
computation121212For more details on this, in particular on the relation
between complexity and entropy, see Subsection 6.1.. At some point, Alice will
necessarily arrive at the state that corresponds to the initial state of the
machine’s computation (right after the machine $U$ has read the prefix $q$),
where simplicity and compactness are maximal. She may call this initial state
the “Big Bang”, and hypothesize that the world had its beginning in this
moment. This is broadly consistent with our actual physical observations. We
will discuss this further in Subsection 6.1.

Clearly, the description of this computational process is not unique. The fact
that we can describe computations in many completely different ways (which
however give equivalent algorithmic probabilities) must have a counterpart in
Alice’s freedom of choosing among different descriptions of her external world
which make equivalent empirical predictions. But this is a phenomenon which is
well-known in many fields of physics. For example, we can choose different
coordinate systems to describe spacetime, or we can prefer to add unobservable
“pilot waves” to our description of quantum mechanics. The nontrivial
prediction is that there exists _some_ simple description in terms of concise
laws of small algorithmic complexity, not that this description is unique.

At the same time, our approach claims that this appearance of an external
world is ultimately not fundamental: according to Postulates 3.2, what
_actually_ determines Alice’s future observations is conditional algorithmic
probability. In particular, her observations do not fundamentally supervene on
this “physical universe”; it is merely a useful tool to predict her future
observations. Nonetheless, this universe will seem perfectly real to her,
since its state is correlated with her future experiences. If the measure
$\mu$ that is computed within her computational universe assigns probability
close to one to the experience of hitting her head against a brick, then the
corresponding experience of pain will probably render all abstract insights
into the non-fundamental nature of that brick irrelevant.

For what follows, it will be useful to formulate our findings within a certain
terminology that has first appeared in the context of the foundations of
quantum mechanics: that of an _ontological model_ HarriganSpekkens ;
SpekkensContextuality . We will be using this notion in a context that differs
somewhat from its originally intended use. The starting point will be to talk
about an _operational theory_ SpekkensContextuality . In the context of
quantum mechanics, this would be a theory that describes _preparation
procedures_ (represented, for example, by quantum states) and _measurements_.
In our context, we can regard an observer in some observer state $x$ as being
subject to a preparation procedure which leads to an _operational state_
${\mathbf{P}}(y|x)$ ($y\in{\mathcal{S}}$). The corresponding measurement
procedure would be to wait for $m$ time steps to see what further bits
$y=y_{1}\ldots y_{m}$ the observer actually acquires131313It is usually
considered crucial in the context of quantum theory that there is not only a
single measurement, but a “choice of measurements”; this is not relevant here.
However, we will make more direct contact with quantum theory in Section 7.
Furthermore, it is of course not necessary that the observer “waits passively”
for her next states; our theory can certainly accommodate a notion of _action_
, but it is not a notion of fundamental importance for our purpose.. If we
adopt this terminology, then the monotone Turing machine computation becomes
an ontological model according to the following definition
SpekkensContextuality :

“An ontological model is an attempt to offer an explanation of the success of
an operational theory by assuming that there exist physical systems that are
the subject of the experiment. These systems are presumed to have attributes
regardless of whether they are being subjected to experimental test, and
regardless of what anyone knows about them. […] Thus, a specification of which
instance of each attribute applies at a given time we call the ontic state of
the system. If the ontic state is not completely specified after specifying
the preparation procedure, then the additional variables required to specify
it are called hidden variables. We shall denote the complete set of variables
in an ontological model by $\lambda$, and the space of values of $\lambda$ by
$\Omega$.”

In more detail, we arrive at the following observation:

######  Observation 4.5 (Computational ontological model).

If we regard the conditional probability ${\mathbf{P}}(y|x)$ (as a function of
$y$) as an operational state preparation in the sense explained above, then
the corresponding state of the computational process which generates the
approximating measure $\mu$ represents an (approximate) _ontological model_.

This “computational ontological model” has a set of states $\Omega$ that
corresponds to the possible configurations of the computational process.
Formulating this process in terms of a monotone Turing machine, preparation of
${\mathbf{P}}(y|x)\approx\mu(y|x)$ amounts to the preparation of a probability
distribution over the configurations $\lambda\in\Omega$, including, for
example, identically independently distributed bits on the unread part of the
input tape. This ontological model is _simple_ (in the sense that it is
expected to have short description length ${\rm K}(\mu)$), probabilistic, and
it evolves in time in a way that has once started in a simple initial state
(“Big Bang”). Its time evolution admits “mechanistic” explanations of the
observer state changes (“I’ve seen the light flash _because_ a particle from
this process has been hitting me.”) We can thus interpret it as an observer’s
_external world_.

Is this “computational ontological model” unique? Even if we pick the monotone
Turing machines as our underlying machine model, and fix our universal
reference machine $U$, there may be more than one program of length ${\rm
K}(\mu)$ which generates $\mu$. If those programs make the machine perform
different computations (which however all lead to an output string statistics
resembling $\mu$), then we have several equally simple computational
ontological models. However, we expect that there are _not too many_ programs
of length ${\rm K}(\mu)$ that generate $\mu$. What we take as evidence for
this conclusion is that there is a well-known analogous statement for standard
Kolmogorov complexity, which says that the number of shortest programs of any
object is bounded by a universal constant, cf. (LiVitanyi, , Exercise 4.3.6).
We conjecture that the mathematical arguments carry over to the complexity
${\rm K}(\mu)$, in which case it would follow that the number of (simplest)
computational ontological models of any computable measure $\mu$ is bounded by
a universal constant.

Arguably, what we call “our universe” _is_ essentially nothing but a (certain
type of) ontological model of our observer state changes, which is useful to
us because it helps us predict future observations, and because it gives us
“mechanistic” explanations of what we see. The arguments above might suggest
that what we call our “physical universe” corresponds exactly to this
computational ontological model. But as I will argue in Section 7, if some
version of our theory applies that involves memory loss (Postulates 3.1), then
there will be an extra layer “between us and the world”, hiding some degrees
of freedom, and leading us to an effective description that displays some
features of quantum theory.

This view suggests some sort of effective _pancomputationalism_ Pancomp : our
(emergent external) world _is_ in some sense a computation. Nevertheless,
there is not necessarily a naive correspondence between the structure of our
world and the causal structure of the computational process as it is usually
envisioned. Other proposals of that kind, including approaches by Zuse Zuse ,
Schmidhuber Schmidhuber , ’t Hooft tHooft  and Lloyd Lloyd , assume a direct
one-to-one mapping between modules of the model of computation (such as
“gates” or “tape cells”) and space-time regions. The approach of this paper
suggests that there is typically only a weak correspondence of this form,
going beyond the proposals just mentioned, as will be discussed in more detail
in Section 7.

##  5 The rise and fall of objective reality

“How come ‘one world’ out of many observer-participants?” (J. A. Wheeler
WheelerInformation ).

In Section 4, we have seen that our approach predicts some features of physics
as we know it: with high probability, observers see simple probabilistic “laws
of nature”, and find themselves to be part of an external world that they may
call “the universe”. However, there is one further crucial aspect of physics
that is _not_ apriori true in our theory: namely that _different observers see
the same physical world_.

Figure 3: Informal illustration of the setup considered in this section. We
have an observer $A$ (Alice) who finds herself to be part of a simple
computational process which generates some measure $\mu$ (according to Theorem
4.4). This means that the computational process is what she may call her
“external world” as explained in Section 4; her observer state (here e.g.
$x=x_{1}x_{2}x_{3}x_{4}$) is a function $f_{A}$ of the process’ state (see
also Figure 2). Suppose that there is another simple computable function
$f_{B}$, acting on the states of this process, which yields another string of
bits that grows over time. Then Alice can interpret this as “having another
observer Bob3rd in her world”, and her world will yield a probability measure
${\mathbf{P}}_{3\rm rd}$ determining what is going to happen to Bob3rd in her
world. However, Bob’s first-person perspective, Bob1st, is governed by
algorithmic probability, ${\mathbf{P}}_{1\rm st}\equiv{\mathbf{P}}$; and these
probabilities may apriori be completely unrelated. In other words, what Bob1st
will probably really see next (symbolized by the grey speech bubble) may be
very different from _what Alice will probably be seeing Bob 3rd see next_. But
as we show in Theorem 5.2 below, for a large number of bits, the conditional
probabilities ${\mathbf{P}}_{1\rm st}$ and ${\mathbf{P}}_{3\rm rd}$ will be
very close to each other — in this sense, Alice and Bob will be “part of the
same world”, and Bob3rd will be a probabilistically faithful “representation”
of Bob1st. This is a probabilistic form of emergent objective reality.

In fact, it is not even clear what it means to talk about “different
observers” in our context. Postulates 3.2 only talk about _observer states_ ,
not about “observers” as physical objects of which you could have two or
three. In principle, we could have a single observer — “the mind” — taking a
never-ending random walk on the observer states, with transitions determined
by algorithmic probability. Or could we? What would this claim even mean? Is
it not empirically obvious that there are _other observers_ out there, not
just _I_?

We certainly believe that there are other observers because we encounter
things in our world that seem to hold first-person perspectives, too: other
humans, for example. Let us now discuss and formalize what this means in our
framework. Suppose that an observer — say, Alice the guinea pig — finds
herself located in some simple, computable, probabilistic external world
(characterized by a computable measure $\mu$ on her observer states), as
derived in detail in Section 4.

Suppose that Alice encounters another guinea pig, called Bob3rd, in her
external world. The subscript indicates that this describes a “third-person
perspective”: Alice points to something (an object, a pattern) in her world
that she calls “Bob”. Moreover, Alice can in principle consider the
information that is stored and processed in Bob3rd’s brain, and reason about
how this information changes in time. Even if it may be impossible for Alice
(or unethical) to open Bob3rd’s brain and read out all this information in
practice, Alice can still argue that it contains _some_ information that
changes over time, in accordance with the evolution of Alice’s world. If this
evolution is probabilistic, then there will be an induced probability
distribution ${\mathbf{P}}_{3\rm rd}$ that describes the distribution of
Bob3rd’s brain states one moment after the other.

But now, if this momentary information content corresponds to a finite binary
string $x$, then our theory enables us to regard this string as an _observer
state_. In other words, we can think of the corresponding first-person
perspective that describes “what it is like” to be in state $x$, and think of
a corresponding abstract observer Bob1st — the actual “mode of being” in this
state141414Note that Bob1st is not a well-defined “object”, but a handy way to
talk about the first-person perspective corresponding to $x$..

Typically, Alice will expect that Bob3rd and Bob1st are in some sense
“identical”. For example, when she observes Bob3rd expressing a feeling of
happiness on seeing Alice (together with the corresponding neural correlates),
she will assume that Bob1st really _does_ have that feeling in some sense. But
is this really true? Given that our theory admits that Bob3rd and Bob1st are
in some sense different things, is such an identification possible and
meaningful?

We certainly cannot formally analyze what it means to “feel” something, but
the question just asked has an obvious formal counterpart: namely, we can
compare two probability measures. On the one hand, we have ${\mathbf{P}}_{3\rm
rd}$, the probability induced by Alice’s world on Bob3rd’s fate; on the other
hand, we have algorithmic probability, ${\mathbf{P}}_{1\rm st}:={\mathbf{P}}$
that determines Bob1st’s actual first-person chances according to Postulates
3.2. Is there any relation between the two?

To put these considerations into a more concrete form, consider the question
whether the sun rises tomorrow. Suppose that Alice has gathered enough
information about her external world, and about the physical measure $\mu$, to
know that there is a probability close to one that the sun is going to rise
tomorrow. Thus, Alice will have a close to 100% chance of _seeing Bob 3rd see
the sun rise tomorrow_. But what is Bob1st’s actual chance to see the sun rise
tomorrow, from his first-person perspective?

###  5.1 Asymptotic coherence of ${\mathbf{P}}_{\rm 1st}$ and
${\mathbf{P}}_{\rm 3rd}$

Let us go into a bit more formal detail. As in Figure 2, we have some
computational process that generates Alice’s states, and a computable function
$f_{A}$ which “reads out” Alice’s current state from the full computational
process. But now, in addition, we have another computable map (random
variable) $f_{B}$ which reads out another observer state, as illustrated in
Figure 3. That is, $f_{B}$ reads out the state of Bob3rd.

Since the computational process is probabilistic, its state at some
computational time151515Note that this does _not_ assume or imply that the
computational process has some “Newtonian” notion of absolute time; it only
means that there is at least one way to parametrize the progression of the
computation, which does not exclude the possibility that the process has a
causal structure that resembles e.g. that of general relativity. $t$ is a
random variable, $g(t)$. For every $t$, the function $f_{A}$ reads out Alice’s
observer state $f_{A}(g(t))$ at that computational moment. Similarly,
$f_{B}(g(t))$ will yield another observer state. If $f_{B}$ is suitably
chosen, then $f_{B}(g(t+1))$ will always be either equal to $f_{B}(g(t))$ or
one bit longer, i.e. the bit string read out by $f_{B}$ will “grow” over time.
For $f_{A}$, this is automatically true due to the way that the output of a
monotone Turing machine is defined.

Because $g(t)$ is a random variable, we have to distinguish the following two
probability distributions:

  1. 1.

The distribution ${\mathbf{P}}_{3\rm rd}$ on $f_{B}(g(t))$ (i.e. on the states
of Bob3rd) that is induced by the probabilities of the different computational
histories $g(t)$;

  2. 2.

the distribution ${\mathbf{P}}_{1\rm st}\equiv{\mathbf{P}}$ which Postulates
3.2 claim to determine what actually happens to Bob1st. This is algorithmic
probability.

In our example, if there is an almost 100% chance that Alice will see that
Bob3rd sees the sun rise tomorrow, then this is a probability assignment of
${\mathbf{P}}_{3\rm rd}\approx 1$. If we ask what Bob1st will actually see,
then this asks for the corresponding value of ${\mathbf{P}}_{1\rm st}$.

Apriori, both probabilities can take different values. However, if they _are_
in fact different, then we have a quite strange situation, reminiscent of
Wittgenstein’s philosophical concept of a “zombie” SEP : Bob1st would in fact
not subjectively experience what Alice sees Bob3rd experience, but would
divert into his own “parallel world” with high probability. This does not mean
that Alice will subsequently be confronted with a “soulless” Bob3rd (since
$f_{B}$ will still produce an observer state, associated with _some_ first-
person perspective); it would somehow, very roughly, mean that Alice is
confronted with some sort of “very unlikely instance” of Bob1st, and that the
Bob1st that she knew earlier has somehow subjectively “fallen out of the
universe”. It is probably save to say that we lack both intuition and
terminology to describe non-mathematically what that would mean161616Note that
this would be much stranger than the simple effect of having different
“computational branches”, following different values that the random variable
$g(t)$ can take. Similarly as in Everettian interpretations of quantum
mechanics, a “many-worlds”-like picture suggests that we should imagine
different “instances” of Alice and Bob, following the different branches.
Nevertheless, if Alice and Bob meet in one branch of an Everettian world, they
will both be subject to the same objective chances of joint future
observations (like seeing the sun rise tomorrow). For “probabilistic zombies”
as just described, this would not be the case..

As we will soon see, the good news is that the properties of algorithmic
probability imply that this strange phenomenon will not typically happen in
every-day situations171717Strictly speaking, this kind of consistency (as
expressed in Theorem 5.2) would not _necessarily_ have to hold in order to
have a well-defined theory; physics would still make sense in a solipsistic
world in which every observer is surrounded by probabilistic zombies. But such
a world would be truly terrifying. (but see Subsection 5.2). Instead,
${\mathbf{P}}_{1\rm st}$ and ${\mathbf{P}}_{3\rm rd}$ _will_ be very close to
each other under natural circumstances. To prove this formally in Theorem 5.2,
we have to carefully specify the assumptions that go into the proof.

######  Assumption 5.1.

Consider observer Alice who is part of an external world as explained in
Subsection 4.2, i.e. of some probabilistic computational process which will be
in some state $g(t)$ at every computational time $\enspace t\in{\mathbb{N}}$.

Let $f_{B}$ be a computable map that assigns to each $g(t)$ (from some $t_{0}$
on) an observer state. We interpret $f_{B}$ as a “locator function” that reads
out the state of Bob3rd as he appears in the computation. We make two
assumptions:

  * •

For every $t\geq t_{0}$, $f_{B}(g(t+1))$ is either equal to $f_{B}(g(t))$ or
one bit longer (otherwise it would not consistently describe the temporal
evolution of an observer state);

  * •

for every $t\geq t_{0}$, there will be some $t^{\prime}>t$ with
$f_{B}(g(t^{\prime}))\neq f_{B}(g(t))$ with unit probability.

The map $f_{B}$ can be interpreted as an “observer localization” of Bob3rd
HutterTOE  inside the computational world. Intuitively, the first assumption
above says that Bob3rd survives indefinitely in Alice’s world, and he never
forgets anything181818This reminds us of the fact that we are working with
deficient Postulates 3.2; memory erasure would be described with Postulates
3.1.. The second assumption says that Bob3rd does not become “eternally
frozen”.

Suppose that Alice encounters Bob3rd at computational time $t_{0}$, and his
state is $z:=f_{B}(g(t_{0}))$. As explained above, there are now two different
conditional probability distributions: on the one hand ${\mathbf{P}}_{\rm
3rd}(y|z)$, i.e. the probability that the state of Bob3rd in Alice’s world
changes in the future by acquiring the next bits $y_{1}y_{2}\ldots y_{m}=y$.
And on the other hand, we have ${\mathbf{P}}_{\rm
1st}(y|z)\equiv{\mathbf{P}}(y|z)$, i.e. the chance that an observer in state
$z$ will, as seen from his first-person perspective, obtain these next bits.

Our assumptions above imply that ${\mathbf{P}}_{3\rm rd}$ is a computable
measure. This has a compelling consequence:

######  Theorem 5.2 (Emergence of objective reality).

In the setting of Assumption 5.1, the probabilities ${\mathbf{P}}_{3\rm rd}$
that determine the fate of Bob3rd within Alice’s external world are
asymptotically close to the actual chances
${\mathbf{P}}\equiv{\mathbf{P}}_{1\rm st}$ of Bob1st’s first-person
perspective. That is, with ${\mathbf{P}}_{3\rm rd}$-probability one,

${\mathbf{P}}_{3\rm rd}(y|z_{1}z_{2}\ldots z_{n})\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}{\mathbf{P}}_{1\rm st}(y|z_{1}z_{2}\ldots
z_{n}),$ (6)

i.e. the difference between the conditional versions of ${\mathbf{P}}_{\rm
3rd}$ and ${\mathbf{P}}_{\rm 1st}$ tends to zero.

This theorem follows from applying Solomonoff induction as formalized in Lemma
4.3 to the computable measure ${\mathbf{P}}_{\rm 3rd}$.

In this sense, Alice and Bob “inhabit the same world” — Bob3rd as encountered
by Alice is a faithful representation of an actual first-person perspective of
some Bob1st. Note that this theorem is formulated _from Alice’s perspective_ :
it is Alice who assigns ${\mathbf{P}}_{3\rm rd}$-probability one to
convergence.

At first sight, this seems to resemble the idea of _Bayesian consistency_
DiaconisFreedman : if two agents start with different prior distributions, but
receive equivalent data, their Bayesian posterior distributions will in many
cases converge towards each other. In this view, both agents are by definition
part of the “same world” such that they receive data which is in principle
compatible between the two, and the prior and posterior distributions
represent their beliefs. In the approach of this paper, however, this not the
case: ${\mathbf{P}}_{\rm 3rd}$ and ${\mathbf{P}}_{\rm 1st}$ are not beliefs
but _actual chances_ , and observers are _not_ assumed to be part of the same
world in the usual sense.

###  5.2 Probabilistic zombies

Theorem 5.2 shows in what sense our theory predicts the _emergence of
objective reality_ : while the fundamental ontology is given by each
observer’s first-person perspective, there is nevertheless a tendency for
observers to agree that they see a specific objective “external world”.
However, this theorem relies on two premises as formalized in Assumption 5.1:

  * •

Bob is “old/complex enough”: the length $n=\ell(z)$ of Bob’s observer state
$z$ must be large.

  * •

Bob “survives and remembers forever”: the locator function $f_{B}$ that is
supposed to read out Bob’s state from Alice’s world will always yield a
consistently growing observer state, even in the very distant future.

While it seems plausible that both assumptions are satisfied _approximately_
in typical situations, they will not hold in all cases. In this subsection and
the next, we will have a closer look at what happens if we drop these two
assumptions. Let us start by dropping the first of the two — namely, that Bob
is “old/complex enough”:

######  Observation 5.3 (Probabilistic zombies).

In the notation of Theorem 5.2, the probabilities ${\mathbf{P}}_{3\rm rd}$
that determine the state of Bob3rd in Alice’s world, and ${\mathbf{P}}_{1\rm
st}\equiv{\mathbf{P}}$ that determine Bob1st’s actual first-person chances,
will in general be very different if the length $n$ ob Bob’s observer state
$z$ is small.

If this is the case, we will say that Bob3rd is a “probabilistic zombie” for
Alice. In particular, this will be the case if Bob’s current state $z$ is _too
simple_ , namely if ${\rm K}(z)\ll{\rm K}({\mathbf{P}}_{3\rm rd})$.

As explained in Section 5, this notion of “probabilistic zombie” vaguely
resembles Wittgenstein’s notion of a zombie SEP , but it is on the one hand
more precise and on the other hand less intuitive. From Alice’s perspective,
it means that Bob3rd does _not_ faithfully (in probability) represent the
actual first-person perspective of some corresponding Bob1st. See the previous
subsection for a more detailed explanation.

Since the complexity ${\rm K}(z)$ tends to grow with $n=\ell(z)$, the
statement that ${\rm K}(z)$ is small can roughly be interpreted as saying that
“Bob is still young”. But this intuition should be taken with a grain of salt,
since there is no monotonous relationship between length and complexity.

In more detail, ${\rm K}(z)$ has to be compared to ${\rm K}({\mathbf{P}}_{\rm
3rd})$, the complexity of the measure ${\mathbf{P}}_{\rm 3rd}$ as defined in
Theorem 2.5. The latter is the length of the shortest program that generates
${\mathbf{P}}_{\rm 3rd}$ an a universal computer — in other words, it is _the
description length of the probabilistic laws of Alice’s world, together with a
description of Bob 3rd’s location $f_{B}$_. We can thus interpret the
quantitative statement in Observation 5.3 as follows: _If Bob 3rd’s complexity
is much smaller than the number of bits it takes to describe the laws of
physics in Alice’s world, _and_ to locate Bob3rd inside that world, then
Bob3rd is a probabilistic zombie for Alice._

We will not formally prove this quantitative statement, but give some
intuition as to why it represents a reasonable conjecture. To this end, let us
return to Theorem 5.2 which proves the asymptotic emergence of objective
reality. Intuitively, if $n$ is large, then Bob’s state $z=z_{1}z_{2}\ldots
z_{n}$ contains enough information to _infer via universal induction, without
reasonable doubt, that this data has been generated by Alice’s world_. In
other words, a description of Alice’s world, and thus of ${\mathbf{P}}_{\rm
3rd}$, can be obtained from $z$. If this can be done via some algorithm, then
we could conclude that

${\rm K}({\mathbf{P}}_{\rm 3rd})\lesssim{\rm K}(z).$

Therefore, if this inequality is very strongly violated, then we expect that
${\mathbf{P}}_{\rm 3rd}\not\simeq{\mathbf{P}}_{\rm 1st}$. Let us go into some
more detail. Consider some enumeration $m_{1},m_{2},m_{3},\ldots$ of the
enumerable semimeasures, and define

$\mathbf{M}_{V}(w):=\sum_{j=1}^{\infty}2^{-{\rm
K}(j)}m_{j}(w)\quad(w\in{\mathcal{S}}\setminus\\{\varepsilon\\}).$ (7)

This is well-defined since $\sum_{j}2^{-{\rm K}(j)}\leq 1$ LiVitanyi . The
resulting semimeasure $\mathbf{M}_{V}$ is enumerable since ${\rm K}(j)$ can be
computably estimated from above, and it is universal by construction.
Therefore, it is the semimeasure corresponding to some universal monotone
Turing machine $V$ in virtue of Definition 2.1. It follows that

$\mathbf{M}_{V}(y|z)=\sum_{j=1}^{\infty}2^{-{\rm
K}(j)}\frac{m_{j}(z)}{\mathbf{M}_{V}(z)}m_{j}(y|z).$ (8)

Starting with this equation, emergence of objectivity as in Theorem 5.2 can be
interpreted intuitively (but not fully rigorously) as follows. Bob’s first-
person probability ${\mathbf{P}}\equiv{\mathbf{P}}_{\rm 1st}\approx\mathbf{M}$
is a mixture of all enumerable semimeasures as in (8). It is as if there was a
“correct” computable measure ${\mathbf{P}}_{\rm 3rd}$ which is not known to
Bob, and hence Bob holds a prior $\mathbf{M}_{V}$, i.e. a prior distribution
over all computable (and merely enumerable) measures (and semimeasures). On
receiving new data $z$, Bob updates his beliefs to $\mathbf{M}_{V}(\cdot|z)$.
At some point, it turns out that a single term of the infinite (sub-)convex
combination dominates: namely, $m_{j}={\mathbf{P}}_{\rm 3rd}$. This can only
happen if

  * •

${\mathbf{P}}_{\rm 3rd}(z)$ is not too small, i.e. Bob’s current state is
“typical” for this distribution;

  * •

${\rm K}(j)$ is not too large, i.e. it is easy to pick ${\mathbf{P}}_{\rm
3rd}=m_{j}$ from the enumeration of semimeasures (intuitively, this amounts to
${\mathbf{P}}_{\rm 3rd}$ itself being simple, i.e. we expect that ${\rm
K}({\mathbf{P}}_{\rm 3rd})\approx{\rm K}(j)$ is also not too large).

  * •

On the other hand, all other $m_{i}$ for $i\neq j$ must either be complex in
comparison (i.e. ${\rm K}(i)\gg{\rm K}(j)$) or represent “worse explanations”
of Bob’s current state than ${\mathbf{P}}_{\rm 3rd}$, in the sense that
$m_{i}(z)\ll{\mathbf{P}}_{\rm 3rd}(z)$.

But if ${\rm K}(z)\ll{\rm K}({\mathbf{P}}_{\rm 3rd})$, then such a
“concentration” on $m_{j}={\mathbf{P}}_{\rm 3rd}$ cannot happen. To see why,
note that from a description of $z$ we can construct a simple algorithm that
generates a computable measure $\mu$ with $\mu(z)=1$, and which has some
arbitrary values for extensions of $z$ (say, ones that differ from
${\mathbf{P}}_{\rm 3rd}$). If $i$ is the simplest index such that $m_{i}=\mu$,
we will thus expect that

${\rm K}(i)\approx{\rm K}(\mu)\lesssim{\rm K}(z)\ll{\rm K}({\mathbf{P}}_{\rm
3rd})\approx{\rm K}(j).$

Therefore, $\mu=m_{i}$ will have much higher weight in (8) than
${\mathbf{P}}_{\rm 3rd}=m_{j}$, and emergence of objectivity will fail: Bob3rd
will be a probabilistic zombie.

###  5.3 Subjective immortality

The next part of our analysis will be to see what happens if we drop the
assumption that “Bob survives and remembers forever”. We all have an intuition
for such situations — a possible scenario is (boldly and humorously)
illustrated in Figure 4. Let us work within the framework of Subsection 5.1:
In Alice’s external world, there is another observer Bob3rd, characterized by
some simple locator function $f_{B}$. Let us assume that, indeed, the
probabilities ${\mathbf{P}}_{\rm 1st}(y|x)$ and ${\mathbf{P}}_{\rm 3rd}(y|x)$