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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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