Skip to main content
addendum
Source Link
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

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.

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.

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.

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.

correction
Source Link
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

NoYes 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 such 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.

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.

No. Suppose you do have such an algorithm. 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.)

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.

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.

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.

Source Link
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

No. Suppose you do have such an algorithm. 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.)

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.