Define a real number $\alpha$ to be computable if there is a computable total function $f_\alpha$ that, given any rational $\epsilon$, yields a rational within $\epsilon$-vicinity of $\alpha$.

Now, assume some principal universal function $U = U(n, x)$ for the class of computable functions. This $U$ generates a certain numbering of computable real numbers: for each computable $\alpha$, its corresponding number is any $n$ such that $U_n = f_\alpha$ (note that every $\alpha$ has infintely many assigned numbers as per Rice's theorem).

Given that, how does one prove the existence of an algorithm that, given any two numbers $n, m$ assigned to any two computable reals $\alpha, \beta$, produces some number that's assigned to their sum $\alpha + \beta$?

So this is a sketch of a proof that came to my mind after writing down this question.

It can be shown that there exists a computable bijection between $\mathbb{N}^2$ and $\mathbb{N}$, so let's denote $[i, j]$ for the natural that corresponds to the pair $(i, j)$ in that bijection. Now define a binary function $F$ such that $F([i, j], \epsilon) = U(i, \epsilon/2) + U(j, \epsilon/2)$. Note that $F$ is clearly computable, and if $i, j$ are indices of some computable reals, then $F_{[i, j]}$ is the function corresponding to their sum.

Since $U$ is principal and $F$ is computable, there exists a computable total $s_F$ such that $\forall n, x : F(n, x) = U(s_F(n), x)$. Combining that with the above, we get that $A(i, j) = s_F([i, j])$ is precisely the algorithm that, given two indices of computable reals, produces an index of their sum.

Does it sound reasonable?

  • $\begingroup$ The result follows from examining the usual proof in real analysis that $\lim (a_n + b_n) = \lim a_n + \lim b_n$, using an $\epsilon/2$ argument. $\endgroup$ – Carl Mummert Dec 3 '18 at 18:47
  • $\begingroup$ Indeed, I was able to prove that $\alpha + \beta$ is computable using that argument. But how do you prove that its index (according to the definitions above) is also computable? $\endgroup$ – 0xd34df00d Dec 3 '18 at 18:50
  • $\begingroup$ In other words, let $f_\alpha$ and $f_\beta$ be the corresponding functions that produce the approximations of $\alpha$ and $\beta$ respectively. The function $f(\epsilon) = f_\alpha(\epsilon/2) + f_\beta(\epsilon/2)$ is computable and provides the required approximations for their sum, but I'm not sure how to find its $U$-index given $U$-indices of $f_\alpha$ and $f_\beta$. $\endgroup$ – 0xd34df00d Dec 3 '18 at 18:54
  • 2
    $\begingroup$ In programming terms, the problem is asking you how to write a program that represents $\alpha + \beta$ given programs that represent $\alpha$ and $\beta$. To do this you need to know what programming language is being used. The choice of $U$ corresponds to the choice of programming language so your answer will depend on how $U$ is defined. $\endgroup$ – Rob Arthan Dec 3 '18 at 20:26

Your Answer

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

Browse other questions tagged or ask your own question.