2 -> to \to

Is a given computable function $f:\mathbb{R}->\mathbb{R}$ f:\mathbb{R}\to\mathbb{R}$differentiable? OK, I'll have to (1) clarify what I mean and (2) show it's not a completely trivial consequence of the halting problem. Part (1): I have to define computability of$f$. Say that a Turing machine computes a real$x$if, given any input$n$, it always returns a sequence of$n$rational numbers, with the$i$th element within$2^{-i}$of$x$. Ie. In other words, it computes the initial part of a Cauchy sequence approximating$x$to a predetermined accuracy. Now we can say that a machine$X$computes$f:\mathbb{R}->\mathbb{R}$f:\mathbb{R}\to\mathbb{R}$ if for any $x$, you can give it a description of a Turing machine to compute $x$ as an input, and always gives you back another one that computes $f(x)$.

It is impossible to make a machine that takes a description of a machine $X$ to compute $f$, and tells you if the function $f$ is differentiable. Ie, i.e. differentiability is undecidable.

But, you say, that's trivial. After all, the machine $X$ we're passing in as argument is, obviously, a machine, so we expect to meet the halting problem. So contrast with:

Part (2): Integration over an interval is computable.

(I've probably made some typos in the above as it's not my field. So try Computable Analysis for more details.)

Is a given computable function $f:\mathbb{R}->\mathbb{R}$ differentiable?

OK, I'll have to (1) clarify what I mean and (2) show it's not a completely trivial consequence of the halting problem.

Part (1):

I have to define computability of $f$. Say that a Turing machine computes a real $x$ if, given any input $n$, it always returns a sequence of $n$ rational numbers, with the $i$th element within $2^{-i}$ of $x$. Ie. it computes the initial part of a Cauchy sequence approximating $x$ to a predetermined accuracy.

Now we can say that a machine $X$ computes $f:\mathbb{R}->\mathbb{R}$ if for any $x$, you can give it a description of a Turing machine to compute $x$ as an input, and always gives you back another one that computes $f(x)$.

It is impossible to make a machine that takes a description of a machine $X$ to compute $f$, and tells you if $f$ is differentiable. Ie. differentiability is undecidable.

But, you say, that's trivial. After all, the machine $X$ we're passing in as argument is, obviously, a machine, so we expect to meet the halting problem. So contrast with:

Part (2): Integration over an interval is computable.

(I've probably made some typos in the above as it's not my field. So try Computable Analysis for more details.)