# Prove the index of the sum of any two computable numbers is computable

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?

• 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. – Carl Mummert Dec 3 '18 at 18:47
• 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? – 0xd34df00d Dec 3 '18 at 18:50
• 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$. – 0xd34df00d Dec 3 '18 at 18:54
• 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. – Rob Arthan Dec 3 '18 at 20:26