# Can real numbers be represented such that addition is computable in an intuitive way?

I want to represent (computable) real numbers in such a way that addition is computable, i.e. there exists a Turing machine $M(x, y, n)$ which halts with the $n$th digit of $x + y$ on its tape.

The most obvious way to encode real numbers is to lead off with a sign bit, i.e. the first digit of a number is 1 if the number is negative or 0 if it is positive. But it seems to me that this will result in addition being non-computable, because $M$ would need to examine an arbitrary number of digits in order to determine if $(x +\epsilon) - x$ is positive.

One thing I could do is to take a continuous bijective function $f:\mathbb R\to[0, 1]$ and encode $x$ as $f(x)$. However, this is very different than how I usually think about the representation of numbers.

Is there a more straightforward way to represent real numbers such that addition is computable? Since all computable functions are continuous, and the sign function is discontinuous, it seems like my intuition about positive versus negative numbers is incompatible with computability.

• Essentially the same argument applied to the $n$th digit rather than the sign bit shows that what you are looking for is impossible: You can't tell whether the integer part of $0.999\ldots + 0.000\ldots$ is nonzero before examining all the digits of the inputs. // On the other hand, if you represent real numbers as Cauchy sequences of rationals, then addition is certainly computable. – Rahul Dec 8 '16 at 23:04
• @Rahul Is it? Doesn't the same problem apply? We don't know what the integer part of the Cauchy sequence:$$(.9,.99,.999,.9999\dotsb)$$is. – Akiva Weinberger Dec 14 '16 at 23:08
• @Akiva: Yes, I should clarify. It sounds like the OP is looking for a representation in terms of digit sequences, so addition is uncomputable if you can't compute the digits of the sum. I suggest a representation in terms of Cauchy sequences, so addition is computable since you can certainly compute a Cauchy sequence converging to the sum. In this representation we no longer need, nor are we allowed to ask for, the digits of a given real number. – Rahul Dec 14 '16 at 23:17
• @Rahul Ah. That seems to have its own problems, though, such as the fact that we never know whether a nonzero real is positive or negative, or whether two reals are within a given $\epsilon$ of each other. (Consider a sequence whose first thousand entries seem to approach $\pi$, and whose remaining entries all equal $-100$.) – Akiva Weinberger Dec 14 '16 at 23:26
• @Akiva: Yes, those are discontinuous functions from $\mathbb R$ to $\{\top,\bot\}$, and discontinuous functions are not computable [1, 2, 3]. (And indeed, the $n$th-digit function is also discontinuous.) – Rahul Dec 14 '16 at 23:33

It's not hard to show that the structure $(\mathbb{Comp}, +)$ (where "$\mathbb{Comp}$" denotes the set of computable reals) is isomorphic to the additive group of the ring $\mathbb{Q}[\pi]$. The latter has a natural computable presentation, hence the former has a (not very natural) computable presentation; that is, there is a structure $(A, \oplus)$, where $A$ is a computable set of natural numbers and $\oplus$ is a total computable binary function, which is isomorphic to $(\mathbb{Comp}, +)$.
The problem, here, is that the unfolding of this interpretation is hard: there is no uniform algorithm to take an element of $A$ and output its decimal expansion (for basically the reason Rahul mentioned in their comment).
• @Xodarap Any two vector spaces with the same dimension over the same field are isomorphic. $\mathbb{Comp}$ and $\mathbb{Q}[\pi]$ are each countably-infinite-dimensional $\mathbb{Q}$-vector spaces, so they're isomorphic. – Noah Schweber Dec 15 '16 at 22:17