# Differentiability of computable functions

Call a computable function a total function $\mathbb{R} \to \mathbb{R}$, for which there exists a Turing machine outputting arbitrary close approximation to $f(x)$ given arbitrary close approximation to $x$.

1. Obviously not every computable function is differentiable (for example, absolute value). For arbitrary continuous functions, the set of points of differentiability is $\Pi_{3}^0$. Can this be improved for computable functions?
2. Suppose $f$ is computable and continously differentiable everywhere. Must $f'$ be computable?
-
Isn't the answer to (2) obviously "yes"? Just plug in the definition of differentiation... –  Daniel Litt Aug 9 '10 at 17:12
I think the problem is that you don't know how far you have to go to get the derivative to a given approximation. –  Torsten Ekedahl Aug 9 '10 at 17:16
I think "given arbitrary close approximation to $x$" should be "given a close enough approximation to $x$". –  Kaveh Aug 9 '10 at 18:24
@Torsten: I took "computable" to mean "given long enough running time, can approximate arbitrarily well". Does the machine have to know how well it's approximating? –  Daniel Litt Aug 9 '10 at 18:47
@Daniel Litt: that is part of the usual definition of a computable function. The question above is somewhat vague about the meaning of "arbitrarily close". The usual definition is: the function $f$ is computable if there is an algorithm that, when given a Cauchy sequence that converges quickly to $r$, produce a Cauchy sequence that converges quickly to $f(r)$. "Converges quickly" means that the Cauchy sequence meets some fixed computable modulus of convergence, e.g. $\forall n \forall m>n ( |a_n - a_m| < 2^{-n})$. –  Carl Mummert Aug 9 '10 at 19:33

John Myhill gave an example of a recursive function defined on a compact interval and having a continuous derivative that is not recursive [Michigan Math. J. 18 (1971), 97-98, MR0280373]. However, Pour-El and Richards have shown that if a recursive function defined on a compact interval has a continuous second derivative, then it has a recursive first derivative [Computability and noncomputability in classical analysis, TAMS 275 (1983), 539-560, MR0682717].

-

You may be interested in some very recent work by Brattka, Miller and Nies looking at points of differentiability for computable functions in terms of algorithmic randomness. Briefly call a real x computably random (Martin-Löf random) if no computable (computably enumerable) martingale succeeds on a binary representation of x. Brattka, Miller and Nies show that:

1) At each computably random real, every computable function that is non-decreasing is differentiable.

2) At each Martin-Löf random real, every computable function of bounded variation is differentiable.

-

you can see this : Derivatives of Computable Functions.

Ning ZhongArticle first published online: 13 NOV 2006

DOI: 10.1002/malq.19980440303