Redundant definition of computable function on $[a,b]$ in Pour-El and Richard book?

87 Views Asked by At

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?

1

There are 1 best solutions below

2
On

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).