Function with no (good) approximation?

Question

Does an (uncomputable) function $f(x)$ exist for which this statement is not true:

$$\forall\varepsilon\in\mathbb{R}_{>0}:\int\limits_{-\infty}^\infty |f(x)-F(x)| \mathrm{dx}<\varepsilon$$

Where $F(x)$ is any computable function.

Best regards

Kevin

Answer 1

I believe you are asking:

Is there a function $f$ such that for some $\epsilon>0$, there is no computable $F$ with $\int_{\mathbb{R}}\vert f-F\vert dx<\epsilon$?

(If not, please clarify.)

Well, first of all, we need to be a bit careful. The notion of "computable function" makes perfect sense on $\mathbb{N}$, but things get a bit tricky when you want to define a computable function on $\mathbb{R}$. However, it turns out that the precise definition of "computable function on the reals" doesn't matter here: all we need is that there are only countably many of them.

Let $\{F_i:i\in\mathbb{N}\}$ list the computable functions on reals, and let $f$ be defined as follows:

• $f(x)=0$ for $x<0$.

• For $x\in [i, i+1)$, we let $f(x)=F(x)+17$.

Then for every computable $F$, we will have $\int_\mathbb{R}\vert f-F\vert dx\ge 17$. Note that this uses nothing about the computable functions except for the fact that there are only countably many of them, so we can prove an identical result for larger classes of functions.

---

Note: The argument above uses "going off to infinity" in a crucial way. If I look instead at functions which are continuous, and live on the (compact) interval $[0, 1]$, then every such function is computably approximable: if $f:[0, 1]\rightarrow\mathbb{R}$ is continuous, then for every $\epsilon>0$ there is a computable continuous $F:[0, 1]\rightarrow\mathbb{R}$ such that $\int_{[0, 1]}\vert f-F\vert dx<\epsilon.$