1.10. The “no-self-defeating object” argument, revisited 27 One can apply Theorem 1.10.19 to various naive halting algorithms. For instance, let P(S) be the program that simulates S for (say) 1000 CPU cycles, and then returns “yes” if S is halted by that time, or “no” otherwise. Then the program G generated by the above proof will take more than 1000 CPU cycles to execute, and so P will determine incorrectly whether G is halted or not. (Notice the similarity here with Proposition 1.10.2.) The same argument also gives a non-counterfactual version of the non- computability of the busy beaver function: Proposition 1.10.20. Let f : N → N be a computable function. Then there exists a natural number n and a program G of length n (and taking no input) that halts in finite time, but requires more than f(n) CPU cycles before it halts. Proof. Let P(S) be the program that simulates S for f(n) CPU cycles, where n is the length of S, and returns “yes” if S is halted by that time, or “no” otherwise. Then the program G generated by Theorem 1.10.19 is such that P does not correctly determine if G halts. Since P is always correct when it returns “yes”, this means that G does halt, but that P(G) returned “no”, which implies that G takes more than f(n) cycles to execute. Of course, once one has a program of length n that runs for more than f(n) CPU cycles, it is not hard to make a program of length a little bit larger than n that outputs a number greater than f(n), so that one can con- clude as a corollary that the Busy Beaver function outgrows any computable function. 1.10.4. Miscellaneous. The strategy stealing argument in game theory is already more or less set up in non-counterfactual form: in any game that admits “harmless moves” (such as noughts and crosses), any strategy of the second player can be stolen to be defeated (or at least held to a draw) by the first player. Similarly for arbitrage strategies in finance (unless there are loopholes due to imperfect information or friction costs). It is a bit more diﬃcult to recast the no-self-defeating objects in physics in a non-counterfactual form, due to the large number of implicit physical assumptions in these arguments. I will present just one simple example of this, which is the grandfather paradox that asserts that controlled time travel is impossible because you could use such travel to go back in time to kill your grandfather before you were born. One can convert this to a slightly less counterfactual format: “Theorem” 1.10.21 (Very imprecisely stated!). Suppose that one has a mechanism in universe U to travel back in time and arrive at universe U . Then there can exist events in U that occurred differently in universe U .

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2013 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.