Computable roots of computable functions

Here are several interesting results from computable analysis:

Theorem 1. If $f$ is a computable function from $\mathbb{R}$ to $\mathbb{R}$ and $\alpha$ is an isolated root of $f$, then $\alpha$ is computable.

Corollary 2. If $p(x)$ is a polynomial over $\mathbb{R}$ with computable coefficients, then every root of $p(x)$ is computable.

Theorem 3. There is a effective closed subset of $\mathbb{R}$ which is nonempty (in fact, uncountable) but which has no computable point.

Theorem 4. There is a computable function from $\mathbb{R}$ to $\mathbb{R}$ which has uncountably many roots but no computable roots.

Continue reading

The logic of Reverse Mathematics

This post is about a research idea I have been thinking about which is quite different from my usual research. It’s an example of a project with an “old fashioned” feel to it, as if it could have been studied 50 years ago. It’s almost a toy problem, so I haven’t spent too long digging through references yet. For all I know it was solved 50 years ago. Continue reading