A definition of computable numbers that requires to "wait an infinite amount of time" to get the correct result; how to make this precise

Question

Consider the following definition:

A number $x \in \mathbb R$ is computable, if there exists a (one-tape) Turing machine which (running infinitely long) writes the binary expansion of $x$ onto its tape.

But even allowing additional working tapes does not change the class of herey defined computable numbers. But does this definition makes sense? How can anybode read off one digit of $x$, as we cannot be sure that it is definite, i.e. it could be changed infinitely often in the run of the machine. So the result is just correct if we "wait an infinite amount" of time. But how to formalize this?

Answer 1

This is not a research-level question, but since the general level of interest seems high, here is an answer. I cannot guess from your question whether you're shooting for something that will result in the usual computable numbers, or you're trying to surpass that.

First we have Turing's definition of computable real number, and it is the one others have been commenting on: a real number $x \in \mathbb{R}$ is said to be computable if any one of the following holds:

1. (Calculation fo approximations) There is a Turing machine $M$ which on input $n$ terminates outputs a pair of integers $(a, b)$ such that $|x - a/b| < 2^{-n}$.
2. (Calculation of digits) There exists a Turing machine $M$ which runs forever and writes out the digits of $x$ on an infinite write-once tape. That is, once it writes a digit, it cannot change it.
3. (Calculation of neighborhoods) There exists a Turing machine $M$ which on input $(p,q)$, where $p$ and $q$ are rational numbers, terminates if, and only if, $p < x < q$.

There are many other equivalent definitions.

We can also ask about various other kinds of computability, and we shall discover a hierachy of classes of reals, see for instance X. Zheng's Classification of the Computable Approximations by Divergence Boundings. One can also study subclasses of computable reals, see again X. Zheng's work. For instance, we can try these:

• (Mind-change computability) A real $x$ is computable with $k$ mind changes if there exists a Turing machine $M$ which runs forever and writes its digits on an output tape. While so doing, it may change its mind about any particular digits at most $k$ times, for some fixed $0 \leq k < \infty$. A variant allows computations where every digit eventually stabilizes, i.e, the number $k$ is not fixed to be the same for all digits.
• (Oracle computation) A real $x$ is computable with oracle $A$ if there is an oracle Turing machine $M$ such that $M^A$ computes $x$ (in any of the senses above).
• (Infinite-time Turing machine computation) A real $x$ is infinite-time Turing computable if there exists an infinite-time Turing machine $M$ which computes $x$ (in any of the senses above).
• (Definable real number) A real $x$ is definable, say in the language of set theory, if there exists a formula $\phi$ such that $\phi(x)$ holds and, if $\phi(y)$ holds for any $y \in \mathbb{R}$ then $y = x$.

I am guessing you had in mind some sort of mind-change computability. It is stronger than the usual computability.

Answer 2

Computing an 'infinite' object is usually defined based on Turing machines with one-way output tape; cmp. Section 2.1 in [Weihrauch'00]. This also asserts closure under composition.

[Turing'36] first defined computability of real numbers based on their binary (historically actually: decimal) and in [Turing'37] corrected himself to consider sequences of rational approximations with error bounds.

A Turing machine allowed to revise each output tape cell a finite but unbounded number of times amounts to Computation in the Limit and corresponds to computing with oracle access to the Halting problem. It is not closed under composition, but climbs up the Arithmetical Hierarchy.

Allowing a machine to discard and restart producing (any finite initial segment of) its infinite output a finite but unbounded number of times, is considered for example in Section 5.1 of [Yours truly'07a] and Sections 3.2+3.3 of [Ziegler'07b].

Answer 3

The standard solution is to require write only tape if you want to use TTE. Obviously you can have RW work tapes.

Another solution is information theoretic (domain theory) and says that you get better and better approximations approximation to the real number as internals and the limit is a single number.

Also keep in mind that decimal representation of real numbers is not good for computability over reals, any computable function is continuous however if you use decimal representation even functions like multiplication will not be computable with the information topology of decimal numbers.

See Klaus Weihrauch's book "Computable Analysis" for more on the topic.

Answer 4

One solution is what Radu GRIGore suggested, namely requiring that every digit becomes fixed after some (finite) number of steps. Of course, this comes with the practical issue that you never know whether a digit is already fixed. For defining computability, this is seems to be fine since the Turing machine is never actually used in practice by someone who wants to read off the digits.

If you anyway do not like this, a possible solution is to consider Turing machines with two tapes, where one of them is a dedicated output tape and the Turing machine is only allowed to write each cell once. This definition appears to be stricter than the one above since the Turing machine needs to be sure that a digit is fixed before writing it on the output tape.

Answer 5

How about, $x\in[0,1]$ is computable if there is a TM $M$ which, on input $n\in\mathbb{N}$, prints the first $n$ digits of the decimal expansion of $x$ and then halts.

Edit (13-Jul-2021). This definition of computable real numbers, though natural (apparently, it's the one Turing gave), has problems. It's better to demand that on input $n$, the TM prints a decimal expansion $y$ such that $|x-y|<1/n$.