1.12. A computational perspective on set theory 39 function call (e.g., digit(π,n)), and if we are allowed to set up an infinite loop in which n starts at 1 and increments indefinitely, one can exhaust all the digits of π, which is good enough for most “practical” mathematical purposes. For instance, if one were allowed to run programs of countable length using real arithmetic, one could make a program that determined whether the digits of π were uniformly distributed or not, or to determine the truth of the Riemann hypothesis, or more generally to compute the truth-value of any first-order sentence in the theory of the real line. We assume that the usual arithmetic operations can be performed on real numbers in reasonable amounts of time. For instance, given two real numbers x,y, one can determine whether they are equal or not in finite time (consulting some sort of “equality oracle” for the reals if necessary). Note that equality can be a subtle issue if one thinks of real numbers as infinite strings of digits, their equality can only be verified directly by using a countable amount of computing power. But we will sidestep the issue of how exactly the reals are implemented by simply assuming that enough oracles exist to perform real arithmetic at an acceptable computational cost. As already hinted at in the above discussion, we are assuming that our computer has access to a certain amount of computing resources (e.g., time, memory, random number generation, oracles). We will be rather vague on exactly how to formalise the concept of a resource, but basically the standard definitions used in computer science would be a good approximation here, at least when the resources are finite. But one can consider allowing for certain computational resources to be infinite in some carefully controlled manner for instance, one could consider a situation in which countably infinite loops are permitted (provided that all variables in the loop that one wants to retain “converge” in some sense at the end of the loop), but for which uncountable loops are not allowed. We will not formalise such concepts here (but roughly speaking, they correspond to allowing transfinite induction up to some specified ordinal, and no further). We will not be using sets or set-theoretic functions in this computer language. However, we will use as a substitute the concept of an oracle - a “black box” routine f() that takes zero or more variables of a given class as input, and returns zero or more variables in various classes as output (usually we will have just a single output, but it will be convenient to allow multiple outputs). Being a black box, we do not know how the oracle obtains the output from the input, but we are able to use the oracle anyway. Let us assume that each invocation of an oracle takes some acceptable amount of time (e.g., bounded time when the computational resources are finite, or countably infinite time if countable time resources are allowed, etc.). All our oracles are consistent in the sense that they always produce the same

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.