2

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!

Anton V.
  • 603

1 Answers1

1

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$

Anton V.
  • 603