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


*

*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?

*Suppose $f$ is computable and continously differentiable everywhere. Must $f'$ be computable?

 A: 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.
A: 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].
A: you can see this :
Derivatives of Computable Functions.
Ning ZhongArticle first published online: 13 NOV 2006
DOI: 10.1002/malq.19980440303
Copyright © 1998 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
