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

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?

• The definition is fine as-is, which is just "eventually the TM will write the correct digit of $x$ to the right place". I agree that one might desire a more workable definition, in which we know when the correct digit is written. Typically you would ask for a computable function $f$ which, given $n$, gives the number of steps $f(n)$ after which the $n$-th digit does not change. One might call this a computable rate of convergence.
– cody
Jan 26, 2017 at 14:03
• I don't understand the definition. What is the output of a machine with infinite running time? And what is actually your question? The standard definition of a computable real is what Aryeh wrote below. Jan 26, 2017 at 15:07
• For each specific instance of time, the machine has written something (or even nothing) on its tape; so the output is well-defined. Imagine pause the machine and look whats written. But the problem is that we can never be sure if the written digits are the correct ones, as at a later instance of time they might get replaced. That quite different than what Aryeh wrote, as in his definition we know at a certain instance of time (i.e. when the machine finishes on processing $n$) that we have a correct digit of the result. Does this make sense? The result would be valid if we wait infinitely long. Jan 26, 2017 at 15:41
• The definition seems well-formed to me. Spelled out: there exists a TM $T$, such that for all $n\in\mathbb{N}$ there is a $t\in\mathbb{N}$ such that for all $t'\ge t$, if you run $T$ for $t'$ steps, then the first $n$ symbols on the tape are the first $n$ bits of $x$. Jan 26, 2017 at 16:57
• Also, I believe I'm not saying anything different from what cody already said, but seemed to be somewhat ignored. Jan 27, 2017 at 10:43

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.

• Thanks for your great answer. What you call infinite-time Turing computable seem to came closest, as @ChristianMatt wrote "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". So I do not bothered about the ability for some "finite" individual to read the result of in his finite amount of time (i.e. by pausing the machine or so). But out of curiosity I would be glad if you can give some reference for what you called "mind-change computability", any articles or books... Jan 27, 2017 at 12:34
• @AndrejBauer Thanks so much for this excellent answer from last year. Can you give a reference to these definitions please "computable with k mind changes", "computable with oracle" etc. - I don't see those specific terms in the Zheng paper you referenced. Thanks! Sep 1, 2018 at 7:29

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].

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.

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.

• Your last sentence seem to nail what I mean, ability to read the digits of (in finite time) is an additional requirement, and I do not wanted to consider that. Jan 27, 2017 at 12:31

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$$.

• Do you think this is equivalent, I conjecture this would give less numbers being computable? Jan 26, 2017 at 14:08
• I don't think the notion of a number produced by an infinitely-running TM is well-defined (as Sasho Nikolov pointed out), so the question of equivalence is moot. Jan 26, 2017 at 15:47
• If you stipulate (as cody did) that the $n$th digit does not change after $f(n)$ steps, then I believe the two are equivalent. Jan 26, 2017 at 20:42
• Woops, I missed the computability requirement. Comment retracted. Jan 27, 2017 at 14:18