Define a number generating machine to be a total turing machine running on input alphabet {0,1} (or, any ary), that given input n (in binary) outputs a digit (binary or decimal or whatever).

Given such a machine $M$, one gets a corresponding real number $\alpha(M) \in \mathbb{R}$, between 0 and 1, defined as $\alpha(M) := \sum_{i=1}^\infty \frac{d_i}{10^i}$ (where the output digits are decimal) where $M$ outputs the digit $d_i$ on input $i$.

Define a number $\alpha \in \mathbb{R}$ to be definable if its fractional part $\lbrace\alpha\rbrace = \alpha - [\alpha]$ is of the above form. It is clear that the set of definable numbers do not vary if the input or the output arity in the definition of number generating machines is changed.

Question: Is the sum of two definable numbers always definable?

More strongly, given number generating machines $M, M'$, can one construct a number generating machine $M''$ for the fractional part of $\alpha(M) + \alpha (M')$?

The answers to both the questions seem to be No, but I couldn't put together a clear argument.

  • 1
    $\begingroup$ Your title would be better stated as: Is the addition of computable real numbers computable? The word decidable is usually applied to sets, when their characteristic function is computable, rather than functions. Your definable numbers are closely related to the concept of computable number used in the subject called computable analysis. In logic and model theory, the term definable number would mean it is the unique objects (in some structrue) satisfying some property expressible in a formal language. This notion often goes well beyond the computable. $\endgroup$ – Joel David Hamkins Jan 28 '10 at 13:56
  • 2
    $\begingroup$ Oh, I now see your comment C in your answer below, indicating that you may not welcome remarks about related ideas that other mathematicians believe to be important. In this case, please ignore my remark. $\endgroup$ – Joel David Hamkins Jan 28 '10 at 14:10

Yes and no. The sum of two computable numbers is always computable, but there is no uniform way to find a decimal expansion for the sum.

Suppose you do have an algorithm for adding any two numbers. Consider adding the numbers .2222... and .7777... Your algorithm should output the first digit of the result after reading only finitely many digits of each number. That digit could be 0 or 9, depending on whether the algorithm thinks the sum is 1.0000... or .9999... Let's say the algorithm never read past the n-th digit of either number. Then the algorithm will return the same answer on any input which agrees with .2222... and .7777... up to the n-th digit. Then, it is easy to change the (n+1)-th digit of each number so that the answer is incorrect for the new numbers. (If the answer was 0, change both (n+1)-th digits to 0; if the answer was 9, change both (n+1)-th digits to 9.)

On the other hand, this kind of problem only arises when the sum could be a number with two distinct decimal representations such as 1.000... = .999... If you know in advance that the result is not of this form, then your algorithm can simply wait until it has read enough digits to decide between 0 and 9. This will always work, provided that you have that additional information so you know you won't wait infinitely long. When the answer does have two decimal representations, it is trivial to come up with a program to write that number. So you can always come up with a machine that will output the desired sum, but there is no way to computable way to detect between the two instances.

In your question, you give a little more than just the decimal presentation, you also give the programs that generate each such presentations. However, the problem persists even with this extra information. Take an inseparable pair of computably enumerable sets V and W. For each n, let An and Bn be the machines that start to output .222... and .777... until such stage s where n enters W or V. If n enters V, then machine An starts outputing 3's instead of 2's after the s-th digit while machine Bn keeps outputing 7's as usual; if n enters W then machine Bn starts outputing 6's instead of 7's after the s-th digit, but An keeps outputing 2's as usual. If there were a uniform way to compute the sum of the outputs of An and Bn, then the first bit of the sum could be used to separate V and W.

For this reason, it is preferable to use a different representation of computable numbers. What is most commonly used are rapidly convergent Cauchy sequences of rationals. There are various ways to formalize these. A common one is to use extended binary representations where the bits -1,0,1 are allowed. Another (very uncommon) one is to use extended decimal representations where the digits 0,1,2,...,9, and 10 are allowed. This fixes the above problem since you can't go wrong by returning the first digit 10 as the answer to the sum of .2222... and .7777... This technique is known as "using nails" in practical implementations of high-precision arithmetic.

  • $\begingroup$ The first paragraph is only an answer to the "More strongly" part of the question, right? $\endgroup$ – Reid Barton Jan 27 '10 at 20:20
  • $\begingroup$ Good point. I didn't read the question carefully. $\endgroup$ – François G. Dorais Jan 27 '10 at 20:26
  • 1
    $\begingroup$ Strictly speaking, this is not a solution to "More strongly" either, since $M$ and $M'$ are not given as black boxes, but as explicit Turing machines. The "more strongly" asks for an algorithm to construct a machine for $\alpha(M)+\alpha(M')$ given machines $M$ and $M'$. The basic question asks for non-constructive existence of such a machine for every pair $M,M'$. $\endgroup$ – Boris Bukh Jan 27 '10 at 20:40

No. With apologies, can I say you did not answer me correctly?

A. The question is very precisely stated. It did not say that given "$\alpha,~~\exists $ a unique $M$ ". If some $M$ hits $\alpha$ (or its fractional part), one is satisfied calling it a definable number.

B. You made the first possible mistake in concluding it's undecidable by the finite-range-of-digits argument. You possibly would be right if there were black-box oracles $M, M'$ giving the nth digits of the summands. Here your input is stronger. You have the whole turing machine (ie. its underlying algorithm) open in your hands. You could possibly infer something about infinitely many of the digits of $\alpha(M)$ in one shot by looking at parts of it.

For example, if the machines were simple (and you knew that they were of that type), generating rational numbers as recurring decimals (as .0000.. or .9999... doesn't matter :)) through a finite state-machine, you could investigate them and could write down an algorithm for the sum. In layman's words: "of course I can add rational numbers!".

While your "finite-range-argument" applies to this special case too, thus invalidating the argument.

C. No interest even remotely close to "what is commonly used" and/or "preferable" has been expressed in the problem statement (in fact, just to avoid these kinds of stray comments, I stayed away from terms like 'computable'/'constructible' and used a rather uncommon term 'definable'). Your answer went randomly away from the direction intended here.

I do realise the above sounds a little harsh, and I apologize to you personally. But they are my points all the same. and by the way, how do you respond to an answer here? I couldn't find any link, so, had to add a new answer. :)

  • $\begingroup$ Sorry, I was careless in my original answer. You need a few points to comment, which I just gave you. $\endgroup$ – François G. Dorais Jan 27 '10 at 20:46
  • $\begingroup$ I had forgotten for a bit, but I finally remembered the trick. It's in my answer now. $\endgroup$ – François G. Dorais Jan 27 '10 at 21:31
  • 1
    $\begingroup$ amaanush seems to have a problem with multiple ids. Lack of an OpenID, system seeing him as a different user each time, etc.. Let us wait until this is corrected? $\endgroup$ – Anweshi Jan 27 '10 at 21:33
  • 2
    $\begingroup$ Regarding C: IMHO you are being way too harsh. It is pretty wrong to view MO as an answer-my-question oracle: this is a place where people interact, and interaction takes many forms. The idea is, I think, to interchange information and knowledge; and I think it is very misguided to complain in the way you do here (a good rule is not to do things for which one immediately apologizes!) I have, for one, learned quite a bit from content in answers that 'randomly went away' from the specific 'point' of the question they were responding to. $\endgroup$ – Mariano Suárez-Álvarez Jan 27 '10 at 21:40
  • $\begingroup$ You missed the adverb "personally" after the phrase "apologize to you". Indeed, what I wrote implies, that I do not apologize as a communicator of mathematics. I started the post stating the earlier post did not answer my question correctly, and I went on to explain why I say so. If you read my post carefully, you will notice that I am not asking anywhere to be "guided". $\endgroup$ – amaanush Jan 27 '10 at 22:46

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.