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.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.