# Is the integral of computable functions computable?

For each $$n$$, let $$f_n$$ be a computable function which takes an infinite binary sequence $$\omega\in 2^\mathbb{N}$$ as its input. $$2^\mathbb{N}$$ has the standard measure (for a finite string $$x=x_1x_2\ldots x_n$$, the set $$\Omega_x$$ of all $$\omega$$ starting with prefix $$x$$ has measure $$2^{-n}$$).

Assuming $$(n,\omega)\mapsto f_n(\omega)$$ is computable, is the function $$n\mapsto \int f_n(\omega) d\omega$$ computable?

I'm pretty sure that this is true, but I can't find a proof (by myself or by looking online). I know that the Cantor space $$2^\mathbb{N}$$ is compact and that computable functions are continuous in this space, but I don't fully see how this can be used to show that the integral is always computable.

Any help would be appreciated!

## 1 Answer

Answering my own question:

First of all, I need to specify the range of $$f_n$$, which are reals. This means that we can think of $$f_n$$ as a Turing machine which given oracle $$\omega$$ and a rational $$\epsilon>0$$, outputs a rational $$r$$ such that $$|r-f_n(\omega)|<\epsilon$$. Denote this $$r$$ with $$f_n^{(\epsilon)}(\omega)$$. Given that $$\int f_n(\omega)d\omega$$ will be a real, we need to show that for a given $$\epsilon$$, we can compute in finite time a rational $$r$$ such that $$|r-\int f_n(\omega)d\omega|<\epsilon$$.

Now some notation: For any $$\omega\in 2^{\mathbb{N}}$$, let $$\omega| m$$ be the string containing the first $$m$$ digits of $$\omega$$. Also, for a finite string $$x$$ of length $$m$$, let $$\Omega_x = \{ \omega\in 2^{\mathbb{N}}: \omega | m=x\}$$. Finally, for a finite string $$x$$, let $$x0_{\infty}$$ be the infinite sequence which starts with $$x$$ and simply adds an infinite amount of zeros at the end.

For any $$\omega$$, the computation of $$f_n^{(\epsilon)}(\omega)$$ uses only a finite part of $$\omega$$, say the first $$m$$ digits. This means that $$f_n^{(\epsilon)}$$ is constant on $$\Omega_{\omega | m}$$. As this holds for any $$\omega$$, these sets $$\Omega_{\omega | m}$$ ($$m$$ can dependent on $$\omega$$) form an open covering of the whole space $$2^{\mathbb{N}}$$. Since $$2^{\mathbb{N}}$$ is compact, there are finitely many $$\Omega_{\omega_1 | m_1}, \Omega_{\omega_2 | m_2},\ldots,\Omega_{\omega_k | m_k}$$ which cover $$2^{\mathbb{N}}$$. This means that for any $$\omega$$, the computation of $$f_n^{(\epsilon)}$$ uses at most $$M=\max\{m_1,m_2,\ldots,m_k \}$$ digits.

The final ingredient is that we can effectively check which digits of $$\omega$$ were used for the computation of $$f_n^{(\epsilon)}(\omega)$$.

Now for the final algorithm: The inputs are $$n$$ and a rational $$\epsilon>0$$. For any $$m\in \mathbb{N}$$, consider the sum $$\sum_{\text{string }x \text{ of length }m} 2^{-m} f_n^{(\epsilon)}(x0_{\infty}).$$ At each step, check if the computation required more than $$m$$ digits, and if it did, move on to $$m+1$$. If for all $$x$$, this did not happen, than $$m=M$$ and the sum above is equal to $$\int f_n^{(\epsilon)}(\omega)d\omega$$, which differs at most $$\epsilon$$ from $$\int f_n(\omega)d\omega$$