2 1. Introduction

details are fairly flexible: with suﬃcient memory, even the simple

language of a programmable calculator is suﬃcient 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 diﬃcult to argue that it allows us to predict coin flips.