addition of definable numbers decidable?

Question

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.

Answer 1

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 A_n and B_n 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 A_n starts outputing 3's instead of 2's after the s-th digit while machine B_n keeps outputing 7's as usual; if n enters W then machine B_n starts outputing 6's instead of 7's after the s-th digit, but A_n keeps outputing 2's as usual. If there were a uniform way to compute the sum of the outputs of A_n and B_n, 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.

Answer 2

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