What computer science has to say about the simulation hypothesis

Abstract The simulation hypothesis has recently excited renewed interest in the physics and philosophy communities. However, the hypothesis specifically concerns computers that simulate physical universes. So to formally investigate the hypothesis, we need to understand it in terms of computer science (CS) theory. In addition we need a formal way to couple CS theory with physics. Here I couple those fields by using the physical Church–Turing thesis. This allow me to exploit Kleene’s second recursion, to prove that not only is it possible for us to be a simulation being run on a computer, but that we might be in a simulation that is being run on a computer – by us . In such a ‘self-simulation’, there would be two identical instances of us, both equally ‘real’. I then use Rice’s theorem to derive impossibility results concerning simulation and self-simulation; derive implications for (self-)simulation if we are being simulated in a program using fully homomorphic encryption; and briefly investigate the graphical structure of universes simulating other universes which contain computers running their own simulations. I end by describing some of the possible avenues for future research. While motivated in terms of the simulation hypothesis, the results in this paper are direct consequences of the Church–Turing thesis. So they apply far more broadly than the simulation hypothesis.