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?
$\endgroup$
6
  • $\begingroup$ Isn't the answer to (2) obviously "yes"? Just plug in the definition of differentiation... $\endgroup$ Aug 9, 2010 at 17:12
  • 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$ 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
    Aug 9, 2010 at 18:24
  • $\begingroup$ @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? $\endgroup$ Aug 9, 2010 at 18:47
  • 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$ Aug 9, 2010 at 19:33

3 Answers 3

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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