Suppose that is a continuous function from to and that we have a program which computes it. (Ignore for now exactly what it means to “compute” a real-valued function of the reals. Suffice it to say that almost every natural continuous function you come across is computable). If we want to compute , say to within an accuracy of , how would we do it, and would we need any further information about in order to do it?
The obvious thing to do is to compute a Riemann sum for some large . However, this could be arbitrarily far from the true value of . For example, might be 0 for all , but might curve sharply up in between each and so that its definite integral is arbitrarily close to 1.
However, since is continuous on , it is uniformly continuous. This means that for all there is a such that whenever , . If we could compute a function such for all , whenever , , then we could compute the definite integral of with arbitrary accuracy: If we want to know to within 0.001, then choose so that and we can take , since .
So, one answer to the question “What extra information do we need in order to compute ?” is: a function witnessing ‘s uniform continuity.
In 1998, Alex Simpson showed, building on ideas of Ulrich Berger and others, that another answer is: Nothing!