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!


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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.