<p>Computing an 'infinite' object is usually defined based on Turing machines with <i>one-way</i> output tape; cmp. Section 2.1 in <a href="http://www.springer.com/gp/book/9783540668176">[Weihrauch'00]</a>.
This also asserts closure under composition.</p>

<p><a href="https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf">[Turing'36]</a> first defined computability of real numbers based on their binary (historically actually: decimal) and in <a href="https://doi.org/10.1112/plms/s2-43.6.544">[Turing'37]</a> corrected himself to consider sequences of rational approximations with error bounds.</p>

<p>A Turing machine allowed to revise each output tape cell a finite but unbounded number of times amounts to <a href="https://en.wikipedia.org/wiki/Computation_in_the_limit">Computation in the Limit</a> and corresponds to <a href="https://en.wikipedia.org/wiki/Super-recursive_algorithm#Inductive_Turing_machines">computing with oracle access to the Halting problem</a>. It is <b>not</b> closed under composition, but climbs up the <a href="https://en.wikipedia.org/wiki/Arithmetical_hierarchy">Arithmetical Hierarchy</a>.</p>

<p>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 <a href="http://dx.doi.org/10.1007/s00224-006-1343-6">[Yours truly'07a]</a> and Sections 3.2+3.3 of <a href="http://dx.doi.org/10.1016/j.entcs.2006.08.015">[Ziegler'07b]</a>.</p>

CC BY-SA 3.0
2017-01-30T11:20:54.867Z
2017-01-30T11:20:54.867Z
Martin Ziegler
<p>The standard solution is to require write only tape if you want to use TTE. Obviously you can have RW work tapes.</p>

<p>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. </p>

<p>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.</p>

<p>See Klaus Weihrauch's book "<a href="https://books.google.ca/books?id=OPolVWVFDJYC" rel="nofollow noreferrer">Computable Analysis</a>" for more on the topic.</p>

CC BY-SA 3.0
2017-01-27T03:08:38.410Z
2017-01-27T11:06:19.897Z
2017-01-27T11:06:19.897Z
Kaveh
<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-01-27T12:31:33.633Z
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.
StefanH
CC BY-SA 3.0
2017-01-26T21:41:02.187Z
2017-01-26T21:41:02.187Z
Christian Matt
<p>How about, <span class="math-container">$x\in[0,1]$</span> is computable if there is a TM <span class="math-container">$M$</span> which, on input <span class="math-container">$n\in\mathbb{N}$</span>, prints the first <span class="math-container">$n$</span> digits of the decimal expansion of <span class="math-container">$x$</span> and then halts.</p>
<p>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 <span class="math-container">$n$</span>, the TM prints a decimal expansion <span class="math-container">$y$</span> such that <span class="math-container">$|x-y|&lt;1/n$</span>.</p>

CC BY-SA 3.0
2017-01-26T14:08:25.090Z
Do you think this is equivalent, I conjecture this would give less numbers being computable?
StefanH
CC BY-SA 3.0
2017-01-26T15:47:30.190Z
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.
Aryeh
CC BY-SA 3.0
2017-01-26T20:42:54.247Z
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.
Aryeh
CC BY-SA 3.0
2017-01-27T14:18:23.823Z
Woops, I missed the computability requirement. Comment retracted.
Aryeh
CC BY-SA 4.0
2017-01-26T14:01:50.573Z
2021-07-13T10:35:30.237Z
2021-07-13T10:35:30.237Z
Aryeh
<p>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.</p>

<p>First we have <a href="https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf">Turing's definition</a> of <strong>computable real number</strong>, 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:</p>

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

<p>There are many other equivalent definitions.</p>

<p>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 <a href="http://www.sciencedirect.com/science/article/pii/S1571066107000199?via%3Dihub">Classification of the Computable Approximations by Divergence Boundings</a>. One can also study <em>subclasses</em> of computable reals, see again <a href="http://link.springer.com/chapter/10.1007%2F11780342_60">X. Zheng's work</a>.
For instance, we can try these:</p>

<ul>
<li><em>(Mind-change computability)</em> A real $x$ is <strong>computable with $k$ mind changes</strong> 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 &lt; \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.</li>
<li><em>(Oracle computation)</em> A real $x$ is <strong>computable with oracle $A$</strong> if there is an <a href="https://en.wikipedia.org/wiki/Oracle_machine">oracle Turing machine</a> $M$ such that $M^A$ computes $x$ (in any of the senses above).</li>
<li><em>(Infinite-time Turing machine computation)</em> A real $x$ is <strong>infinite-time Turing computable</strong> if there exists an <a href="https://arxiv.org/abs/math/9808093">infinite-time Turing machine</a> $M$ which computes $x$ (in any of the senses above).</li>
<li><em>(Definable real number)</em> A real $x$ is <strong>definable</strong>, 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$.</li>
</ul>

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

CC BY-SA 3.0
2017-01-27T12:34:55.607Z
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...
StefanH
CC BY-SA 4.0
2018-09-01T07:29:18.573Z
@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!
zs1
CC BY-SA 3.0
2017-01-27T06:33:25.613Z
2017-01-30T21:18:16.170Z
2017-01-30T21:18:16.170Z
Andrej Bauer
<p>Consider the following definition:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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?</p>

CC BY-SA 3.0
2017-01-26T14:03:33.060Z
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
CC BY-SA 3.0
2017-01-26T15:07:33.613Z
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.
Sasho Nikolov
CC BY-SA 3.0
2017-01-26T15:41:34.337Z
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.
StefanH
CC BY-SA 3.0
2017-01-26T16:57:21.483Z
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$.
Radu GRIGore
CC BY-SA 3.0
2017-01-26T19:26:14.740Z
@RaduGRIGore what you wrote is well-defined, but the OP says "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." This does not sound like your definition in which every digit "settles" after finite time. Maybe Stefan can clarify if this is what he meant.
Sasho Nikolov
CC BY-SA 3.0
2017-01-27T10:41:08.297Z
@SashoNikolov: Your quote is not from the definition, but from a comment that follows. In interpreted that comment as an attempt to relate the definition given above to the usual definition. In the definition given above, I interpreted "infinity" in the sense of a limit. The way I understand the original question is this: "Does it make a difference if we require or not the stability time to be computable?" Andrej Bauer seems to answer this question with "yes", if I understand correctly. (He also answers many other questions ...)
Radu GRIGore
CC BY-SA 3.0
2017-01-27T10:43:57.593Z
Also, I believe I'm not saying anything different from what cody already said, but seemed to be somewhat ignored.
Radu GRIGore
<computability><turing-machines><computable-analysis>
A definition of computable numbers that requires to "wait an infinite amount of time" to get the correct result; how to make this precise
StefanH
# A definition of computable numbers that requires to "wait an infinite amount of time" to get the correct result; how to make this precise

(Asked by: username_0 on 2017-01-26)

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?

**Tags:** computability, turing-machines, computable-analysis
> **Comments:**
> **username_1**: 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*.  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_3**: 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$.  
> **username_2**: @RaduGRIGore what you wrote is well-defined, but the OP says "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." This does not sound like your definition in which every digit "settles" after finite time. Maybe Stefan can clarify if this is what he meant.  
> **username_3**: @SashoNikolov: Your quote is not from the definition, but from a comment that follows. In interpreted that comment as an attempt to relate the definition given above to the usual definition. In the definition given above, I interpreted "infinity" in the sense of a limit. The way I understand the original question is this: "Does it make a difference if we require or not the stability time to be computable?" Andrej Bauer seems to answer this question with "yes", if I understand correctly. (He also answers many other questions ...)  
> **username_3**: Also, I believe I'm not saying anything different from what cody already said, but seemed to be somewhat ignored.  

---

## 5 answers

### Answer by username_8 on 2017-01-27. Score: 16 | Accepted answer

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](https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf) 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](http://www.sciencedirect.com/science/article/pii/S1571066107000199?via%3Dihub). One can also study *subclasses* of computable reals, see again [X. Zheng's work](http://link.springer.com/chapter/10.1007%2F11780342_60).
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](https://en.wikipedia.org/wiki/Oracle_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](https://arxiv.org/abs/math/9808093) $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.

> **Comments:**
> **username_0**: 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...  
> **username_9**: @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!  

---

### Answer by username_4 on 2017-01-30. Score: 4

Computing an 'infinite' object is usually defined based on Turing machines with *one-way* output tape; cmp. Section 2.1 in [[Weihrauch'00]](http://www.springer.com/gp/book/9783540668176).
This also asserts closure under composition.

[[Turing'36]](https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf) first defined computability of real numbers based on their binary (historically actually: decimal) and in [[Turing'37]](https://doi.org/10.1112/plms/s2-43.6.544) 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](https://en.wikipedia.org/wiki/Computation_in_the_limit) and corresponds to [computing with oracle access to the Halting problem](https://en.wikipedia.org/wiki/Super-recursive_algorithm#Inductive_Turing_machines). It is **not** closed under composition, but climbs up the [Arithmetical Hierarchy](https://en.wikipedia.org/wiki/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]](http://dx.doi.org/10.1007/s00224-006-1343-6) and Sections 3.2+3.3 of [[Ziegler'07b]](http://dx.doi.org/10.1016/j.entcs.2006.08.015).


---

### Answer by username_5 on 2017-01-27. Score: 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](https://books.google.ca/books?id=OPolVWVFDJYC)" for more on the topic.


---

### Answer by username_6 on 2017-01-26. Score: 2

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.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_7 on 2017-01-26. Score: 2

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

> **Comments:**
> **username_0**: Do you think this is equivalent, I conjecture this would give less numbers being computable?  
> **username_7**: 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.  
> **username_7**: 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.  
> **username_7**: Woops, I missed the computability requirement. Comment retracted.  

---

