The trouble is that there could be a program that happens to compute a primitive recursive function, but is not literally written with the limited resources of primitive recursion.
Here is an example. Let $f(n)$ be an arbitrary primitive recursive function. Create a function $h$ that does the following:
- Given input $n$, search for a pair of twin primes large than $n$. In other words, search for primes $p,q$ with $n < p$ and $q= p+2$.
- If that search does find a pair of twin primes larger than $n$, return $f(n)$.
This function $h$ is computable. If there are infinitely many pairs of twin primes, then the function $h$ is the same as $f$, and so is primitive recursive. Otherwise, at some point the function $h$ becomes undefined because the searches never terminate. In the latter case, $h$ is not primitive recursive because it is not even total.
How would you determine based on the algorithm above whether $h$ is primitive recursive? That determination would allow us to tell whether there are infinitely many twin primes, which is a famous open question.
The moral is that a particular index might happen to compute a primitive recursive function even though it does not literally appear to be a primitive recursive function. As you say, Rice's theorem gives a proof that the set of indices that happen to compute primitive recursive functions is not decidable.
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$
Best Answer
I think the proof to show that that the set of computable function is countable is far more basic than what you have above.
All partial computable functions can be enumerated by natural numbers. This is essentially the existence of the universal Turing Machine. Hence there are only countably many partial computable functions. The total computable functions are just those partial computable functions that happen to be totally defined. Hence the total computable functions are a subset of the countable set of partial computable functions. Subset of countable sets are countable.