The simulation hypothesis has recently excited renewed interest, especially in the physics and philosophy communities. However, the hypothesis specifically concerns {computers} that simulate physical universes, which means that to properly investigate it we need to couple computer science theory with physics. Here I do this by exploiting the physical Church-Turing thesis. This allows me to introduce a preliminary investigation of some of the computer science theoretic aspects of the simulation hypothesis. In particular, building on Kleene's second recursion theorem, I prove (...) that it is mathematically possible for us to be in a simulation that is being run on a computer \textit{by us}. In such a case, there would be two identical instances of us; the question of which of those is ``really us'' is meaningless. I also show how Rice's theorem provides some interesting impossibility results concerning simulation and self-simulation; briefly describe the philosophical implications of fully homomorphic encryption for (self-)simulation; briefly investigate the graphical structure of universes simulating universes simulating universes, among other issues. I end by describing some of the possible avenues for future research that this preliminary investigation reveals. (shrink)

The important recent book by Schurz ( 2019 ) appreciates that the no-free-lunch theorems (NFL) have major implications for the problem of (meta) induction. Here I review the NFL theorems, emphasizing that they do not only concern the case where there is a uniform prior—they prove that there are “as many priors” (loosely speaking) for which any induction algorithm _A_ out-generalizes some induction algorithm _B_ as vice-versa. Importantly though, in addition to the NFL theorems, there are many _free lunch_ theorems. (...) In particular, the NFL theorems can only be used to compare the expected performance of an induction algorithm _A_, considered in isolation, with the expected performance of an induction algorithm _B_, considered in isolation. There is a rich set of free lunches which instead concern the statistical _correlations_ among the generalization errors of induction algorithms. As I describe, the meta-induction algorithms that Schurz advocates as a “solution to Hume’s problem” are simply examples of such a free lunch based on correlations among the generalization errors of induction algorithms. I end by pointing out that the prior that Schurz advocates, which is uniform over bit frequencies rather than bit patterns, is contradicted by thousands of experiments in statistical physics and by the great success of the maximum entropy procedure in inductive inference. (shrink)

This is the first of two papers that use off-training set (OTS) error to investigate the assumption-free relationship between learning algorithms. This first paper discusses the senses in which there are no a priori distinctions between learning algorithms. (The second paper discusses the senses in which there are such distinctions.) In this first paper it is shown, loosely speaking, that for any two algorithms A and B, there are “as many” targets (or priors over targets) for which A has lower (...) expected OTS error than B as vice versa, for loss functions like zero-one loss. In particular, this is true if A is cross-validation and B is “anti-cross-validation” (choose the learning algorithm with largest cross-validation error). This paper ends with a discussion of the implications of these results for computational learning theory. It is shown that one cannot say: if empirical misclassification rate is low, the Vapnik-Chervonenkis dimension of your generalizer is small, and the training set is large, then with high probability your OTS error is small. Other implications for “membership queries” algorithms and “punting” algorithms are also discussed. (shrink)

The epistemic arrow of time is the fact that our knowledge of the past seems to be both of a different kind and more detailed than our knowledge of the future. Just like with the other arrows of time, it has often been speculated that the epistemic arrow arises due to the second law of thermodynamics. In this paper, we investigate the epistemic arrow of time using a fully formal framework. We begin by defining a memory system as any physical (...) system whose present state can provide information about the state of the external world at some time other than the present. We then identify two types of memory systems in our universe, along with an important special case of the first type, which we distinguish as a third type of memory system. We show that two of these types of memory systems are time-symmetric, able to provide knowledge about both the past and the future. However, the third type of memory systems exploits the second law of thermodynamics, at least in all of its instances in our universe that we are aware of. The result is that in our universe, this type of memory system only ever provides information about the past. We also argue that human memory is of this third type, completing the argument. We end by scrutinizing the basis of the second law itself. This uncovers a previously unappreciated formal problem for common arguments that try to derive the second law from the “Past Hypothesis”, i.e., from the claim that the very early universe was in a state of extremely low entropy. Our analysis is indebted to prior work by one of us but expands and improves upon this work in several respects. (shrink)

We introduce a framework that can be used to model both mathematics and human reasoning about mathematics. This framework involves stochastic mathematical systems (SMSs), which are stochastic processes that generate pairs of questions and associated answers (with no explicit referents). We use the SMS framework to define normative conditions for mathematical reasoning, by defining a “calibration” relation between a pair of SMSs. The first SMS is the human reasoner, and the second is an “oracle” SMS that can be interpreted as (...) deciding whether the question–answer pairs of the reasoner SMS are valid. To ground thinking, we understand the answers to questions given by this oracle to be the answers that would be given by an SMS representing the entire mathematical community in the infinite long run of the process of asking and answering questions. We then introduce a slight extension of SMSs to allow us to model both the physical universe and human reasoning about the physical universe. We then define a slightly different calibration relation appropriate for the case of scientific reasoning. In this case the first SMS represents a human scientist predicting the outcome of future experiments, while the second SMS represents the physical universe in which the scientist is embedded, with the question–answer pairs of that SMS being specifications of the experiments that will occur and the outcome of those experiments, respectively. Next we derive conditions justifying two important patterns of inference in both mathematical and scientific reasoning: (i) the practice of increasing one’s degree of belief in a claim as one observes increasingly many lines of evidence for that claim, and (ii) abduction, the practice of inferring a claim’s probability of being correct from its explanatory power with respect to some other claim that is already taken to hold for independent reasons. (shrink)

In Newcomb’s paradox you can choose to receive either the contents of a particular closed box, or the contents of both that closed box and another one. Before you choose though, an antagonist uses a prediction algorithm to accurately deduce your choice, and uses that deduction to fill the two boxes. The way they do this guarantees that you made the wrong choice. Newcomb’s paradox is that game theory’s expected utility and dominance principles appear to provide conflicting recommendations for what (...) you should choose. Here we show that the conflicting recommendations assume different probabilistic structures relating your choice and the algorithm’s prediction. This resolves the paradox: the reason there appears to be two conflicting recommendations is that the probabilistic structure relating the problem’s random variables is open to two, conflicting interpretations. We then show that the accuracy of the prediction algorithm in Newcomb’s paradox, the focus of much previous work, is irrelevant. We end by showing that Newcomb’s paradox is time-reversal invariant; both the paradox and its resolution are unchanged if the algorithm makes its ‘prediction’ after you make your choice rather than before. (shrink)

There are four types of information an agent can have concerning the state of the universe: information acquired via observation, via control, via prediction, or via retrodiction, i.e., memory. Each of these four types of information appear to rely on a different kind of physical device. However it turns out that there is some mathematical structure that is common to those four types of devices. Any device that possesses that structure is known as an “inference device”. Here I review some (...) of the properties of IDs, including their relation with Turing machines, and quantum mechanics. I also review the bounds on the joint information about the physical universe that can be held by any set of IDs. These bounds constrain the possible mathematical structure of any universe that contains agents with information concerning that universe in which they are embedded. (shrink)