The n-Category Café

Nick Bostrom, director of Oxford University’s impressive sounding ‘Future of Humanity Institute’ wrote a paper - Are You Living In a Computer Simulation? - on a similar theme.

Abstract:

This paper argues that at least one of the following propositions is true: (1) the human species is very likely to go extinct before reaching a “posthuman” stage; (2) any posthuman civilization is extremely unlikely to run a significant number of simulations of their evolutionary history (or variations thereof); (3) we are almost certainly living in a computer simulation. It follows that the belief that there is a significant chance that we will one day become posthumans who run ancestor-simulations is false, unless we are currently living in a simulation. A number of other consequences of this result are also discussed.

A synopsis appeared in the New Scientist in November.

[…] it’s a thousand times more likely that we’re living in a simulation than in the real world […]

My problem with statements like that is that I first seem to know what they mean, but once I think about it a little harder I realize that maybe I canot give them any precise meaning at all.

The great thing about what Scott Aaronson does is that he also thinks similar thoughts, but then manages to deduce from them a theorem that equates two complexity classes, namely

As an easy consequence, he gets the corollary that $\mathbf{PP}$ is “closed under intersection”.

(this is explained in the last three paragraphs)

This is an honest theorem, which is now part of our body of mathematical knowledge.

David Corfield wrote:

Finally, statistical mechanics is described as a ‘hodgepodge of approaches’, and the theory as not having been given much philosophical scrutiny, but to the extent it has not even which questions to pose are clear.

Perhaps some of the questions which pertain to statistical mechanics are hiding in the discussions about weak vs. strong emergence?

Christine, I assume the application of directed algebraic topology to concurrent systems is an outgrowth of the work of Herlihy and Shavit, which was done in the late 90s and won the 2004 Gödel Prize.

You might want to communicate with Prakash Panangaden at McGill about your work. He appears to have worked, as a theoretical computer scientist, on concurrent and distributed systems and also on quantum computing, and has a strong interest in the causal structure of general relativity and its connection to abstract notions arising in computer science.

Hi Christine, you probably already know that Carl Petri, one of the founders of Concurrent Systems as a field of study, used to propound the view that an adequate semantics for concurrency would need to be sufficiently broad to also encompass physics.

From what I’ve been reading recently on Anima ex Machina blog he’s updated this position somewhat to a more “out-there” Universe-is-a-Petri-net kind of stance. He might be right! (as might Smolin – I saw your Amazon review!) On the same page I linked you can also find thoughts of Seth Lloyd and some others on this topic from a conference in Berlin last year.

You’re probably also familiar with Vaughan Pratt who clearly thinks very deeply on this sort of topic (although his publications can be frighteningly dense).

When I was a CS student as Glasgow they used to ask us questions like the “big simulation” argument, just to freak us out. I was never able to see why this would confuse a hardy theoretical physicist though — surely they’d be interested (in theory) in the turtle at the bottom of the tower, ie the real simulation that presumably has to simulate itself?!

I’m looking forward to seeing where the quantum lambda-calculus course goes with this kind of thing. Quantum computation seems to rely on arbitrary-precision complex amplitudes — but having gone to all the trouble of defining True and False as morphisms in the course, surely we won’t now be allowed to pull high-precision complex numbers out of the hat? If you were designing a programming language they’d need to be defined and computed themselves somehow… who “computes” these amplitudes that they’re relying on?

Let me see if I understand what you’re getting at. If there are correlations among a set of concurrent processes, they must be constrained to avoid deadlocks. Perhaps the necessary constraints induce correlations and anti-correlations among states and state transitions in the system that resemble correlations among quantum states. These correlations also imply that the system avoid parts of its state space.

You seem to be assuming discretization at the outset, insofar as the number of concurrent processes is finite, and the associated state space is finite. Should I assume that you have in mind a continuous analog of a set of concurrent processes?

Here is a simple and fairly concrete model you might want to examine. Consider the state space to include a set of n Boolean variables, and the concurrent processes to be n Boolean transition functions of two variables that yield a “subsequent” state for each of the variables. The processes (transition functions) share resources in the significant sense that each of the functions operates on two variables, at least one of which might be used as an input by another function. What would constitute a deadlock in such a system, and what is required to avoid it? Is there necessarily a stochastic component to the system’s behavior? That is, does the transition structure have to rearrange itself every so often, in a way that can’t be described deterministically? I realize this is a very sketchy problem formulation.

By the way, with respect to the relevance of algebraic topology, the set of transition functions in this simple model can be considered as defining an abstract simplicial complex; the Boolean variables are the vertices and the functions define the edges. (Remember however that these functions have some internal structure, since we have 16 distinct, albeit interrelated, Boolean functions to choose from.) My previous questions can then be posed as questions about the “moves” that can and must occur within this complex, in order to avoid certain “pathologies” in the evolution of the system. (By the way, in this light, the collection of transition functions can be loosely regarded as a “gas” of edges [1-D!] which is evolving in parallel with and necessarily coupled to a “gas” of Boolean state variables.)

One more point: The Boolean variables are of course undergoing transitions with successive “time steps”. One might ask if one can define a causal order on these transitions or “events”. That is, given one such event, can one say that it was preceded in a well-defined way by another set of events, and followed accordingly by yet another set of events? It is not immediately evident how such a description is to be derived from the transition functions, although one might plausibly expect that it should be possible.

(I have in mind here a complementary description in terms of causal sets. By the way, regarding the compatibility of discreteness based on causal sets with Lorentz invariance, see Discreteness without symmetry breaking: a theorem [1 May 2006].)

Reasoning about events when there are multiple people who you could be is tricky stuff.

Just for the record, it might be worth pointing out that when Aaronson talks about “kill yoursef if …” in his talk, he is entertaining his audience with a bizarre story involving people and their lives.

I think the point is that there is a precise statement which is supposed to be illustrated by this, but which does not involve people and their lives.

Like there is a complexity class $\mathbf{NP}$ which was originally described as “assume you have a probabilistic computer that can guess the right choice of path each time”, Aaronson introduces a complexity class $\mathbf{PostBQP}$ which is described like: “assume you have a quantum quantum computer and you happen to know that you are doing a measurement on it with the desired outcome”.

Maybe one should rather address this as being inspired by the anthropic principle. It boils down to thinking about a posteriori probabilities.

Presumably halfers and thirders disagree over the equality of different complexity classes.

I would rather think that the difference is in what they think the problem means precisely. That’s my point here: as soon as we try to make precise what we actually mean by all these stories, all mystery disappears.

Here is one way to make the “Sleeping Beauty”-problem precise:

Write a computer program, $A$, that first generates a random number in $\{0,1\}$ and stores that in the variable $\mathrm{rnd}$.

If that number is 1 then the program sends a ping to a given port.

If the number is 0, then the program first sends a ping to the given port, then it goes into a for-loop of 100 cycles that does nothing else, and after that it sends another ping to the given port.

Now your task is to write another program, $B$, which is run once for each ping.

$B$ may return either 0 or 1. Your task is to program $B$ such that the correlation of this return value with the random number $\mathrm{rnd}$ stored by $A$ is high (without reading it out).

Is there any ‘halfer’ around who would want to offer his alternative interpretation of the “sleeping beauty problem”?