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 suﬃcient 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