2
$\begingroup$

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?

$\endgroup$
  • 6
    $\begingroup$ 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. $\endgroup$ – cody Jan 26 '17 at 14:03
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Jan 26 '17 at 15:07
  • $\begingroup$ 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. $\endgroup$ – StefanH Jan 26 '17 at 15:41
  • 1
    $\begingroup$ 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$. $\endgroup$ – Radu GRIGore Jan 26 '17 at 16:57
  • 1
    $\begingroup$ Also, I believe I'm not saying anything different from what cody already said, but seemed to be somewhat ignored. $\endgroup$ – Radu GRIGore Jan 27 '17 at 10:43
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – StefanH Jan 27 '17 at 12:34
  • $\begingroup$ I asked an expert to give a good reference. $\endgroup$ – Andrej Bauer Jan 27 '17 at 13:19
  • $\begingroup$ $o < x < q$ should be $p < x < q$ $\endgroup$ – Tyilo Jan 30 '17 at 20:50
  • $\begingroup$ Thanks, fixed. Can't you just edit it the answer yourself? $\endgroup$ – Andrej Bauer Jan 30 '17 at 21:18
  • $\begingroup$ @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! $\endgroup$ – user1176505 Sep 1 '18 at 7:29
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you think this is equivalent, I conjecture this would give less numbers being computable? $\endgroup$ – StefanH Jan 26 '17 at 14:08
  • $\begingroup$ 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. $\endgroup$ – Aryeh Jan 26 '17 at 15:47
  • $\begingroup$ 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. $\endgroup$ – Aryeh Jan 26 '17 at 20:42
  • $\begingroup$ Woops, I missed the computability requirement. Comment retracted. $\endgroup$ – Aryeh Jan 27 '17 at 14:18
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – StefanH Jan 27 '17 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.