1.1. Approach 3 I would like to highlight a bit of the mindset of computability the- ory here. Computability theorists pay close attention to uniformity. A nonuniform proof of computability proves some program exists to compute the function, and typically has some ad hoc component. A uniform proof explicitly builds such a program. A common example is showing explicitly that there is a program P that computes f(n) provided n N for some fixed, finite N, and considering f com- putable despite the fact that P may completely fail at finding f(n) for 0 n N (in computability theory, functions are on the natural numbers see §3.4 for why that is not as stringent a restriction as it may seem). P is sufficient because for any given sequence of N numbers, there is a program Q that assigns those numbers in order as f(0) through f(N 1), and uses P to find the output for larger numbers. The function we want to compute must have some fixed sequence of outputs for the first N inputs, and hence via the appro- priate Q it may be computed. It is computable, although we would need to magically (that is, nonuniformly) know the first N outputs to have the full program explicitly. Nonuniformity in isolation is not a problem, but it reduces the possible uses of the result. We will discuss uniformity from time to time as more examples come up. Computability theorists more often work in the realm of the non- computable than the computable, via approximations and partial computations. Programs that do not always give an output are seen regularly on certain inputs such a program may just chug and chug and never finish. Of course, the program either gives an output or doesn’t, and in many areas of mathematics we would be able to say “if the program halts, use the output in this way if not, do this other computation.” In fact we could do that in computability theory, but the question of whether any given program halts is a noncomputable one (see §4.1). Typically we want to complete our constructions us- ing as little computational power as we can get away with, because that allows us to make stronger statements about the computability or noncomputability of the function we have built. To succeed in such an environment, the construction must con- tinue while computations are unfinished, working with incomplete and possibly incorrect assumptions. Mistakes will be made and need
Previous Page Next Page