1
$\begingroup$

Triggered by an IMO extremely interesting question & Mathematics Stack Exchange, asked by Dal:

And a link in one of the comments that could have served as an answer but it didn't. (Warning. Norton Internet Security blocked an intrusion from this page; I don't know how serious that is):

Theorem. All well-defined computable functions are continuous.
[ Proof. ] Consider Cauchy's definition of continuity. The function $f$ is continuous at $x$ if for all $\epsilon$, there exists a $\delta$ such that whenever $|y-x|<\delta$, $|f(y)-f(x)|<\epsilon$. There's another way of phrasing that. $f$ is continuous at $x$ if for any $\epsilon$ there is a $\delta$ such that even if the argument, $x$, to $f$ has an error of $\delta$, $f(x)$ still has an accuracy of $\epsilon$. So now think about exact reals defined by Cauchy sequences. Suppose $f$ is a well-defined function, as above. Then to find $f(x)$ to within $2^m$ we just need to find the $m$-th term in the Cauchy sequence $f$ returns. If $f$ is a computable function, it obviously can only examine a finite number of elements of the sequence of $x$. Suppose the latest element in the sequence it looks at is the $n$th one. Then if $f$ is implemented correctly it's managing to compute $f(x)$ to an accuracy of $2^m$ even though its input was only known to an accuracy of $2^n$. In other words, $f$ is continuous. (Choose $m$ such that $2^m<\epsilon$ and $\delta<2^n$.)

There is another thing, seemingly unrelated to it. But I don't believe that things may be unrelated and yet are quite similar in mathematics.
In intuitionistic mathematics, Brouwer's Continuity Theorem boldly states that all total real functions are (uniformly) continuous on the unit interval. Somewhat more elaborate/general: any (total real) function which is defined everywhere at an interval of real numbers is also continuous at the same interval. With other words: for real valued functions, just being defined is very much the same as being continuous. All constructively well-defined functions are continuous.
Oh well, more or less. But anyway, the similarity with the same property for computable functions is clear herewith.

Question. Is the abovementioned similarity just a coincidence? Or is there a deeper reason for it? How exactly may computable and constructive be related to each other?

Sad remark. It's difficult to find good references for Brouwer's Continuity Theorem at the internet nowadays. I took the freedom to make a mirror of this relevant one available:

Disclaimer. The above is more or less what I understand of Brouwer's Continuity Theorem. For me, as a physicist by education, there doesn't seem to be an essential difference between constructive and computable. But that may be short-sighted. Hence the question.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.