Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?
share|improve this question
    
Isn't the answer to (2) obviously "yes"? Just plug in the definition of differentiation... –  Daniel Litt Aug 9 '10 at 17:12
3  
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
1  
@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
show 1 more comment

3 Answers 3

up vote 19 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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