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