Differentiability of computable functions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T22:30:35Z http://mathoverflow.net/feeds/question/35021 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35021/differentiability-of-computable-functions Differentiability of computable functions sdcvvc 2010-08-09T16:49:24Z 2010-08-10T21:47:07Z <p>Call <strong>a computable function</strong> 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$.</p> <ol> <li>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?</li> <li>Suppose $f$ is computable and continously differentiable everywhere. Must $f'$ be computable?</li> </ol> http://mathoverflow.net/questions/35021/differentiability-of-computable-functions/35025#35025 Answer by François G. Dorais for Differentiability of computable functions François G. Dorais 2010-08-09T17:30:35Z 2010-08-10T21:47:07Z <p>John Myhill gave an example of <em>a recursive function defined on a compact interval and having a continuous derivative that is not recursive</em> [Michigan Math. J. 18 (1971), 97-98, <a href="http://www.ams.org/mathscinet-getitem?mr=280373" rel="nofollow">MR0280373</a>]. 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 [<em>Computability and noncomputability in classical analysis</em>, TAMS 275 (1983), 539-560, <a href="http://www.ams.org/mathscinet-getitem?mr=682717" rel="nofollow">MR0682717</a>].</p> http://mathoverflow.net/questions/35021/differentiability-of-computable-functions/35072#35072 Answer by Adam Day for Differentiability of computable functions Adam Day 2010-08-10T02:59:58Z 2010-08-10T02:59:58Z <p>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&#0246;f random) if no computable (computably enumerable) martingale succeeds on a binary representation of x. Brattka, Miller and Nies show that:</p> <p>1) At each computably random real, every computable function that is non-decreasing is differentiable.</p> <p>2) At each Martin-L&#0246;f random real, every computable function of bounded variation is differentiable.</p> http://mathoverflow.net/questions/35021/differentiability-of-computable-functions/35101#35101 Answer by Hashem sazegar for Differentiability of computable functions Hashem sazegar 2010-08-10T11:25:02Z 2010-08-10T11:25:02Z <p>you can see this : Derivatives of Computable Functions.</p> <p>Ning ZhongArticle first published online: 13 NOV 2006</p> <p>DOI: 10.1002/malq.19980440303</p> <p>Copyright © 1998 WILEY-VCH Verlag GmbH &amp; Co. KGaA, Weinheim</p>