13
$\begingroup$

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?
Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ I think the problem is that you don't know how far you have to go to get the derivative to a given approximation. $\endgroup$
    – Torsten Ekedahl
    Commented Aug 9, 2010 at 17:16
  • $\begingroup$ I think "given arbitrary close approximation to $x$" should be "given a close enough approximation to $x$". $\endgroup$
    – Kaveh
    Commented Aug 9, 2010 at 18:24
  • 2
    $\begingroup$ @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})$. $\endgroup$
    – Carl Mummert
    Commented Aug 9, 2010 at 19:33

3 Answers 3

Reset to default
22
$\begingroup$

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

Improve this answer
$\endgroup$
8
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .