1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Rahul Dec 8 '16 at 23:04
  • 1
    $\begingroup$ @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. $\endgroup$ – Akiva Weinberger Dec 14 '16 at 23:08
  • 2
    $\begingroup$ @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. $\endgroup$ – Rahul Dec 14 '16 at 23:17
  • 1
    $\begingroup$ @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$.) $\endgroup$ – Akiva Weinberger Dec 14 '16 at 23:26
  • 1
    $\begingroup$ @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.) $\endgroup$ – Rahul Dec 14 '16 at 23:33
2
$\begingroup$

Rahul's comment essentially kills off any hope of a natural answer to your question. However, there is a very silly answer.

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).

$\endgroup$
  • $\begingroup$ In such a representation, you can't get multiplication, right? (Also, hi.) $\endgroup$ – Akiva Weinberger Dec 14 '16 at 23:10
  • $\begingroup$ Do you have more information/a link about this? It's not obvious to me that those two groups are isomorphic. $\endgroup$ – Xodarap Dec 15 '16 at 22:14
  • 1
    $\begingroup$ @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. $\endgroup$ – Noah Schweber Dec 15 '16 at 22:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.