2 1. Introduction
details are fairly flexible: with sufficient memory, even the simple
language of a programmable calculator is sufficient to implement all
computable functions. An explicit definition is in §3.2.
Most computable functions, by this definition, are completely in-
feasible today, requiring centuries to run and more memory than cur-
rently exists on the planet. Why should we include them? One reason
is that if we require feasibility, we have to draw a line between fea-
sible and infeasible, and it is unclear where we ought to draw that
line. A related reason is that if we do not require feasibility, and
then we prove a function is noncomputable, the result is as strong as
possible: no matter how much computing technology improves, the
function can never be automated. A major historical example of such
a proof is described in the next section, and more are in §4.5, from a
variety of mathematical fields. These unsolvable problems are often
simple statements about basic properties, so intuition may suggest
they should be easy to compute.
A rigorous and general definition of computability also allows
us to pin down concepts that are necessarily noncomputable. One
example is randomness, which will be explored in more depth in §9.2.
If a fair coin is flipped repeatedly, we do not expect to be able to
win a lot of money betting on the outcome of each flip in order.
We may get lucky sometimes, but in the long run whatever betting
strategy we use should be essentially equivalent in success to betting
heads every time: a fifty percent hit rate. That is an intuitive notion
of what it means for the flip outcomes to be random. To turn it
into mathematics we might represent betting strategies as functions,
and say that a sequence of flips is random if no betting strategy is
significantly better than choosing heads every time. However, for any
given sequence of coin flips C, there is a function that bets correctly
on every flip of C. If the class of functions considered to be betting
strategies is unrestricted, no sequences will be random, but intuition
also says most sequences will be random. One restriction we can
choose is to require that the betting function be computable; this ties
into the idea that the computable functions are those to which we
have some kind of “access.” If we could never hope to implement a
function, it is difficult to argue that it allows us to predict coin flips.
Previous Page Next Page