In Pour-El and Richard Computability in Analysis and Physics page $25,$ they defined computable function on $[a,b]$ as follows:

Let $[a,b]$ be such that $a$ and $b$ are computable real numbers. A function $f:[a,b]\to \mathbb{R}$ is computable if:

  1. $f$ is sequentially computable, that is, $f$ maps every computable sequence of points $x_k\in [a,b]$ into a computable sequence $(f(x_k))$ of real numbers;

  2. $f$ is effectively uniformly continuous, that is, there is a computable function $d:\mathbb{N}\to \mathbb{N}$ such that for all $x,y\in [a,b]$ and all $N,$ $$|x-y|\leq\frac{1}{d(N)} \quad\text{implies}\quad |f(x)-f(y)| \leq 2^{-N}.$$

Here comes my question.

Question: Why do we need effectively uniform continuity in definition of computable function?

From several paragraphs before the definition, Pour-El and Richard mentioned the following:

From the point of view of the analyst, a real function $f$ is determined if we know (a) the values of $f$ on a dense set of points, and (b) that $f$ is continuous. Definition above effectivizes these notions.

It seems that if we want a real-valued computable function on $[a,b]$ to behave like a continuous function. Wouldn't effectively pointwise continuity suffice instead of effectively uniformly continuity?

  • $\begingroup$ First a point where I'm a little confused: if that last quote is before the quoted definition, why do they say "Definition above"? Second, does the fact that continuity on a compact set implies uniform continuity have any bearing on your question? $\endgroup$ – Quinn Culver Mar 13 at 18:53

There are many possible definitions of a computable function from $[a,b]$ to $\mathbb{R}$. This definition is one of the most restrictive. At the same time, the definition is interesting because is allows the authors to develop many facts about computable analysis without making too many additional assumptions, and without having to refer directly to computable functionals. The authors remark about this on p. 25 when they say they want to choose a definition that is "couched in the traditional notions of analysis" rather than one that refers to computable functionals.

The purpose of assuming uniform continuity, in general, is that it gives much more information about the function. In general, it is not always possible to compute a modulus of uniform continuity knowing only that a function is continuous at each point of $[a,b]$.

The authors also give an example in Theorem 6 on page 67 of a function that has property (1) from the definition but not property (2).

  • $\begingroup$ I see. Can you give an example illustrating continuous on a compact interval does not allow us to compute modulus if uniform continuity? $\endgroup$ – Idonknow Mar 13 at 22:43
  • $\begingroup$ I am not sure of an example for this particular notion of computability, although I would conjecture there is one in the literature. The challenge for me is the particular definition of computability, which is not the one I typically work with. What you are asking, in my jargon, is for an example of a Banach-Mazur computable function that has no computable modulus of uniform continuity. The paper "A sequentially computable function that is not effectively continuous at any point" by Peter Hertling addresses a similar problem, doi.org/10.1016/j.jco.2006.05.004 $\endgroup$ – Carl Mummert Mar 14 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.