How does one prove that a programming language can calculate every (computable) real number?

Question

Inspired from my previous question, Are there measurements of how much "information" is required to construct given (real) numbers?, I've written a very simple programming language to calculate real numbers. Essentially, in this language, every valid script outputs a Cauchy sequence. Its programs are written on the level of binary, so its size is generally tiny. For instance,

110111111100010000110000 calculates $e$, while

111100010100110101111111000100001110001010101101001000 calculates $\pi$.

We may conclude, therefore, that the Kolmogorov complexity of $\pi$ is larger than $e$, with respect to this language (assuming these are the smallest programs for $e$ and $\pi$).

This is insightful, but the immediate problem is,

How can we be sure that this language faithfully represents the computable reals, in the sense that one could, in theory, write a script for any computable real?

Would it be equivalent to show that this language is Turing complete, or is the ability to calculate any computable real a weaker condition, in which case there is an easier proof?

Answer 1

Let us examine what Alan Turing did in his 1936 paper "On computable numbers, with an application to the Entscheidungsproblem" (Proc. LMS 2(42):230-265). This is the paper which introduced Turing machines, and among other things argued that those numbers which they can compute, coincide with what we ought to regard as "computable". In Sections 9 and 10, Turing proposes three arguments:

1. The way that a Turing machine works is enough to capture a reasonable idea of what any person or machine would do, in the course of calculating something. There are finitely many possible "states of mind", finitely many symbols that you could distinguish one from another, and you are only ever looking at some local chunk out of the entirety of what you've been writing so far. This is primarily an appeal to intuition.
2. The class of Turing-machine-computable numbers is at least as powerful as various other possible characterizations of "computable". In particular, Turing's paper examines David Hilbert's functional calculus and Alonzo Church's notion of "effective calculability". The latter was already shown by Church ("An unsolvable problem of number elementary theory", Amer. J. Math. 58(2):345-363, 1936) to be equivalent to his and Stephen Kleene's $\lambda$-definability. There are many results of this kind in relation to other computational models.
3. Many numbers that we would want to deem "computable", actually can be computed by Turing machines. Kleene made similar arguments in relation to $\lambda$-definability ("A theory of positive integers in formal logic", in two parts, Amer. J. Math 57(1):153-173 and 57(2):219-244, 1935). Your examples of $e$ and $\pi$ are like this. As you note, this is establishing a lower bound on "computability", but it's still rhetorically useful. In Turing's case, the examples would help readers who have never seen a Turing machine before to understand how they work, and in particular reassure them that the simple rules of operation really are capable of doing things like computing Bessel functions.

When you speak of showing that a computational system is Turing-complete, that's an argument of type 2 above. Crucially, by showing that your system is equivalent in power to a Turing machine, you also show that it coincides with all those other Turing-equivalent systems, and with the intuitive argument about why "Turing-computable numbers" are the right class of numbers. If you can prove this equivalence then all of that comes for free.

It could also be the case that Graviton-computable numbers aren't the same as Turing-computable numbers, which would be worth knowing. They could still represent an interesting or useful class of numbers, for some reason that you might be able to justify.

As far as how to prove or disprove equivalence, there are several options since there are many Turing-equivalent systems known. The right target in your case might not be Turing machines, depending on how you've formulated your programming system. It is a matter of convenience.