Why Turing’s Computable Numbers Are Only Non-Constructively Closed Under Addition

Kolmogorov complexity asks whether a string can be outputted by a Turing Machine (TM) whose description is shorter. Analogously, a real number is considered computable if a Turing machine can generate its decimal expansion. The modern ϵ-approximation definition of computability, widely used in practical computation, ensures that computable reals are constructively closed under addition. However, Turing's original 1936 digit-by-digit notion, which demands the direct output of the n-th digit, presents a stark divergence. Though the set of Turing-computable reals is not constructively closed under addition, we prove that a Turing machine capable of computing x+y non-constructively exists. The core constructive computational barrier arises from determining the ones digit of a sum like 0.333¯+0.666¯=0.999¯=1.000¯. This particular example is ambiguous because both 0.999¯ and 1.000¯ are legitimate decimal representations of the same number. However, if any of the infinite number of 3s in the first term is changed to a 2 (e.g., 0.33…32…+0.666¯), the sum's leading digit is definitely zero. Conversely, if it is changed to a 4 (e.g., 0.33…34…+0.666¯), the leading digit is definitely one. This implies an inherent undecidability in determining these digits. Recent papers and our work address this issue. Hamkins provides an informal argument, while Berthelette et al. present more complicated formal proof, and our contribution offers a simple reduction to the Halting Problem. We demonstrate that determining when carry propagation stops can be resolved with a single query to an oracle that tells if and when a given TM halts. Because a concrete answer to this query exists, so does a TM computing the digits of x+y, though the proof is non-constructive. As far as we know, the analogous question for multiplication remains open. This, we feel, is an interesting addition to the story. This reveals a subtle but significant difference between the modern ϵ-approximation definition and Turing's original 1936 digit-by-digit notion of a computable number, as well as between constructive and non-constructive proof. This issue of computability and numerical precision ties into algorithmic information and Kolmogorov complexity.