21
$\begingroup$

Given any computable number $a_c$, is there any algorithm to decide whether it is transcendental?

Definition of “computable number”: According to Ming Li and Vitanyi, a real number $x=0.x_1x_2\ldots$ is lower semicomputable if the set of rationals below $x$ is recursively enumerable. A number $−x$ is upper semicomputable if $x$ is lower semicomputable. A number $x$ is computable (equivalently, recursive) if it is both lower semicomputable and upper semicomputable. I think that this is equivalent to the Turing definition.

$\endgroup$
6
  • 3
    $\begingroup$ What do you mean by computable? $\endgroup$
    – Bumblebee
    Oct 29, 2014 at 11:26
  • 1
    $\begingroup$ @Nilan,According to Ming Li and Vitanyi,A real number $x = 0.x_1x_2 \dots$ is lower semicomputable if the set of rationals below $x$ is recursively enumerable. A number $-x$ is upper semicomputable if $x$ is lower semicomputable. A number $x$ is computable,equivalently, recursive, if it is both lower semicomputable and upper semicomputable. I think it is equivalent to Turing definition. $\endgroup$
    – XL _At_Here_There
    Oct 29, 2014 at 11:34
  • 9
    $\begingroup$ A computable real number is simply a number that can be approximated to any desired accuracy by a program that is guaranteed to halt. $\endgroup$
    – TonyK
    Oct 29, 2014 at 11:41
  • $\begingroup$ @TonyK: Thank you. That is completely new concept for me. $\endgroup$
    – Bumblebee
    Oct 29, 2014 at 11:45
  • 6
    $\begingroup$ There is not even an algorithm that can decide if a computable number is rational. $\endgroup$
    – MJD
    Oct 29, 2014 at 11:46

5 Answers 5

Reset to default
34
$\begingroup$

No. For any $n$, define

$a_n = \begin{cases} \pi/2^r, & \text{if Turing machine $n$ halts in $r$ steps on input $n$} \\ 0, & \text{if Turing machine $n$ never halts on input $n$} \end{cases} $

$a_n$ is computable; we can approximate it to any desired accuracy. But if you could determine whether $a_n$ was transcendental or not, you would have solved the Halting Problem.

$\endgroup$
9
  • 1
    $\begingroup$ So the set of computable transcendental is c.e. set ,and the set of computable algebraic numbers is something like productive set? This means we can give computable function which maps computable algebraic numbers bijectively to a productive set $\endgroup$
    – XL _At_Here_There
    Oct 29, 2014 at 11:54
  • 1
    $\begingroup$ To clarify, as it took me a second: $a_n$ is transcendental iff Turing Machine $n$ halts, and $a_n$ is computable. As the halting problem cannot be solved, there exists an $n$ for which we cannot prove that Turing Machine halts, and hence an $a_n$ for which we cannot prove it is transcendental, but that $a_n$ is still computable. $\endgroup$
    – Yakk
    Oct 29, 2014 at 14:56
  • 2
    $\begingroup$ @Yakk: I don't think that's quite right. What we can say is that it's impossible to write a program that takes $n$ as input, and outputs TRUE if $n$ halts and FALSE if it doesn't. When you say "there exists an $n$", you are in murky waters. $\endgroup$
    – TonyK
    Oct 29, 2014 at 16:10
  • 3
    $\begingroup$ @TonyK Let $X$ be the TM that takes as input $n$. It then starts enumerating all syntactically valid proofs (easy in most formal systems). For each proof, it checks if it is a proof that TM $n$ halts (easy). If so, it outputs 1. It then checks if it is a proof that TM $n$ does not halt. If so it outputs 0. Otherwise it continues running. $X$ halts on input $n$ if and only if there is a proof that says if TM $n$ halts. If for every $n$ there is a proof if TM $n$ halts, then $X$ solves Halt. As $X$ does not solve Halt, the result follows. Flaw? $\endgroup$
    – Yakk
    Oct 30, 2014 at 2:38
  • 1
    $\begingroup$ @Yakk: I retract my comments! You have persuaded me. $\endgroup$
    – TonyK
    Oct 30, 2014 at 3:02
11
$\begingroup$

Note that you are not asking whether a particular real number is computable - you are asking whether the set of transcendental reals is computable.

In general, if a set of real numbers is computable then it is an open set. This is because, given a real number in the set, your algorithm for computing the set must halt after finitely many steps to say that the real number is in the set. But you can only determine a finite amount of information about the real number in that finite number of steps. The set of other real numbers that agree on that finite amount of information is open, and they will also be accepted by your algorithm. So the set of numbers accepted is open.

Now, if you can decide whether an arbitrary number is in a set, you can also decide whether an arbitrary number is not in the set. So if a set of real numbers is computable, then its complement is computable. But then its complement is also open.

So in the end a set of reals that is computable must be closed and open. There are only two such sets in the reals: the empty set and the set of all reals. Those are the only computable sets of real numbers.

This is one example of how the topology of a space affects computability on the space. Because the real line is connected, any computable subset of the real line would have to be clopen. The only two clopen subsets of $\mathbb{R}$ are $\emptyset$ and $\mathbb{R}$.

Things would be different if we look a the Baire space $\omega^\omega$. This space has lots of clopen sets. Not all of them are computable, but at least there are clopen subsets of Baire space that are neither empty nor the whole space.

Sometimes people get worried about this sort of proof, and they ask about the similar problem where, instead of being given an oracle for the real number, they are given an index for a program to compute the real number. They think, maybe this new problem will be computable, since it seems weaker, But, as a matter of practice, if a particular problem is uncomputable when the input is given as an oracle, it will still be uncomputable if the input is given as an index, as long as the other "parameters" of the problem are sufficiently effective.

The proof given by TonyK in another answer shows how to do this. The set $T$ of transcendentals is not closed. In particular, $0 \not \in T$, but $\pi/n$ is in $T$ for each $n$, and $\lim_m \pi/n = 0$. Assume for a contradiction that $T$ was computable. Then we can make a program that does the following:

Begin to enumerate a decimal expansion of $0$, and simultaneously run the decision procedure for $T$ on my own index. If the procedure says my number is in $T$, keep enumerating $0$ forever. If the procedure says my number is not in $T$ switch to enumerating an expansion of $\pi/n$ for some $n$ large enough that the finite decimal expansion I've enumerated so far is an initial segment of the decimal expansion of $\pi/n$.

That quote gives a computable real number (using Kleene's recursion theorem) and the decision procedure cannot give the right answer for that real. But, underneath the hood, the quoted algorithm is just leveraging the topological fact that the transcendentals are not closed, which is the real obstacle.

$\endgroup$
6
  • $\begingroup$ This is not quite correct. We are not given the number in form of a black box oracle that tells us a digit upon request, instead we may assume that we are in fact given a method to compute those digits and can inspect the method. If we only observe that an oracle always returns "$3$" as $n$th digit, we cannot conclude that the number is $\frac13$, because the oracle might give a different answer later; but given a Turing machine that boils down to a function int getdigit(int n) { return 3; } we can prove that the number is $\frac13$ (and we have full information about the number) $\endgroup$
    – Hagen von Eitzen
    Oct 29, 2014 at 20:52
  • $\begingroup$ Carl, you have misunderstood me, the precondition is that the given number is computable, so what I ask is about algorithm which can divide the set into two subset,one is the set of computable transcendental number, another is the set of algebraic numbers. I know there is no decidable algorithm on such a problem. So an interesting problem is that the set of computable transcendental number can 1-1 reducible to creative set? or the complement of the set of computable transcendental number that is in this case,set of algebraic numbers can be 1-1 reducible to productive set? $\endgroup$
    – XL _At_Here_There
    Oct 30, 2014 at 0:28
  • $\begingroup$ But I have to thank you for your answer which is knowledgible of computability. $\endgroup$
    – XL _At_Here_There
    Oct 30, 2014 at 0:31
  • $\begingroup$ @XL_at_China: the uncomputability of the problem I described immediately leads to the uncomputability of the problem you described. In general, as an intuition, you want to think about these sorts of things with the input given as an oracle, in the way I described. If that problem is uncomputable, then the corresponding problem with the input given as an index will be uncomputable as well, as a matter of practice, by just re-working the undecidability proof in a routine manner. $\endgroup$
    – Carl Mummert
    Oct 30, 2014 at 0:58
  • $\begingroup$ @XL_at_China: what do you mean precisely by "the computable transcendental numbers can be 1-reduced to a creative set"? Do you really mean the set of computable transcendental numbers, or do you mean the set of indices of computable transcendental numbers? Rice's theorem will apply to that index set. $\endgroup$
    – Carl Mummert
    Oct 30, 2014 at 1:17
4
$\begingroup$

This is much too ambitious. There is not even an algorithm that can decide if a given computable number is rational.

Maybe you want to say “Just compute the decimal expansion and see if it repeats.” But that is not an algorithm; it never halts on any input.

When you have a computable number, all you have in general is a computer program for generating digits. You can generate any finite number of digits. But no finite number of digits is enough to determine if the number is rational or irrational.

Maybe you think you can figure whether a program produces a repeating output without actually executing it. But you cannot.

$\endgroup$
9
  • 3
    $\begingroup$ @tonyk The question says we are given a computable number $a_c$. The one thing you can do with a computable number $a_c$ is, for a given $N$, calculate in finite time the $N$th bit of $a_c$. There is no way to turn this into an algorithm to decide whether $a_c>1$, but that does not change that fact that one can (by definition) compute any finite number of digits of $a_c$. Contrary to your claim, I can certainly generate the first digit of any computable number. That may suffice to decide $a_c>1$, but in general it does not, since the first digit might be $1$. $\endgroup$
    – MJD
    Oct 29, 2014 at 17:04
  • 3
    $\begingroup$ "The one thing you can do with a computable number $a_c$ is, for a given $N$, calculate in finite time the $N$th bit of $a_c$." No, this is wrong. Given $\epsilon > 0$, you can calculate a rational number $q$ such that $|q-a_c| < \epsilon$; but this does not let you calculate any specific bit of $a_c$. See my first comment. $\endgroup$
    – TonyK
    Oct 29, 2014 at 17:59
  • 3
    $\begingroup$ “We could also define a computable number to be one for which there is a Turing machine which, given $n$ on its initial tape, terminates with the $n$th digit of that number [encoded on its tape]. … This definition is equivalent to that of 9.2.” Marvin Minsky 1967, Computation: Finite and Infinite Machines, p. 159. $\endgroup$
    – MJD
    Oct 29, 2014 at 18:05
  • 2
    $\begingroup$ (Minsky's 9.2 is also the definition used by Turing (1936) in “On computable numbers, with an application to the entscheidungsproblem”; see pp. 232–233: “A sequence is said to be computable if it can be [printed] by a circle-free [that is, guaranteed halting] machine. A number is computable if it differs by an integer from the number computed by a circle-free machine.” $\endgroup$
    – MJD
    Oct 29, 2014 at 18:16
  • 3
    $\begingroup$ @MJD: the definition is equivalent for particular computable numbers - a number is computable in one sense if and only if its computable in the other. But in general there is no uniform procedure that, given a quickly converging Cauchy sequence of rationals, produces a decimal expansion of its limit. $\endgroup$
    – Carl Mummert
    Oct 30, 2014 at 1:01
4
$\begingroup$

To add a small layer of emphasis to what's been written so far: you say 'given a computable number $a_c$', but — unlike the case with using integers as input — you can't really be given a number per se; instead, what you're given as input has to be seen as (equivalent to) a program for computing the number. Viewed in this light, it's no surprise that Rice's theorem comes into play.

By contrast, in a computation model where reals (and integers) are 'atomic' and the atomic operations are e.g. addition/subtraction, multiplication/division, and comparison, then the set of algebraic numbers is c.e.; one can simply dovetail evaluation of all of the possible integer-valued polynomials to test whether the number in question is a root. (I believe that in this model transcendentality is non-computable, and in fact that it's the equivalent of $\Pi_1^0$-complete, but don't hold me to that.)

$\endgroup$
2
  • $\begingroup$ But if we restrict the input to computable numbers, isthe set of algebraic numbers is c.e? And transcendentality is still non-computable? $\endgroup$
    – XL _At_Here_There
    Oct 30, 2014 at 2:58
  • $\begingroup$ @XL_at_China My point is that you need to define exactly what your input is - 'computable number' isn't an input in and of itself, unless you're talking about a model where real numbers are atomic. $\endgroup$
    – Steven Stadnicki
    Oct 30, 2014 at 3:47
0
$\begingroup$

There certainly isn't any known such algorithm since it is currently unknown whether or not $\pi+e$ is transcendental, but under any reasonable definition you'd give of constructibility I believe this number will be constructible.

Considering the difficulty involved in establishing transcendence of numbers, it is highly unlikely that any such algorithm exists in general. Any more detailed answer will require you to first define 'constructible'.

$\endgroup$
3
  • $\begingroup$ Interestingly, it doesn't really matter about the difficulty of proving transcendence or non-transcendence; just the connectedness of the real line prevents any nontrivial set from being computable. $\endgroup$
    – Carl Mummert
    Oct 29, 2014 at 15:15
  • $\begingroup$ As some of the other answers demonstrate, it's not just "highly unlikely that any such algorithm exists", it's known that no such algorithm exists, as a simple consequence of the undecidability of the halting problem. $\endgroup$
    – David Richerby
    Oct 30, 2014 at 8:35
  • $\begingroup$ Just to clarify that I gave this answer before OP clarified the notion of computable. Hence the slightly reserved tone in the answer. $\endgroup$
    – Ittay Weiss
    Oct 30, 2014 at 9:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .