# Decidability of transcendental numbers

I have a question, whose answer is probably well known, but I can't seem to find anything meaningful after a bit of searching, so I would appreciate some help.

My question is whether it is known that deciding whether a number is transcendental is undecidable.

Possibly, one assumes as input, say a program that returns the i^th bit of the number. Thanks in advance for any pointers.

• If reals are represented by programs computing a given bit, or programs computing rational approximations, or any similar kind of programs, then the only decidable sets of reals are the trivial ones (i.e., those that contain either all computable reals or no computable reals), by Rice’s theorem. Commented Mar 2, 2012 at 16:32
• How is that implication shown? $\:$
– user6973
Commented Mar 3, 2012 at 8:24
• My opinion is that transcendence should be decidable. Here a sketch of my "proof", based on the fact that integer coefficient polynomials are countable: math.stackexchange.com/questions/4222372/… Commented Aug 12, 2021 at 8:29
• But IMHO, your question includes two DIFFERENT sub-questions: * transcendence of a given number is decidable? * transcendence of a given number is computable? Commented Aug 12, 2021 at 8:32
• It seems likely that it is not just undecidable, but at least $\Pi_2$-hard (or $\Sigma_2$-hard, depending on the exact question). See e.g. cstheory.stackexchange.com/a/53857/8237 . Commented Feb 4 at 18:38

The subset of transcedental numbers is not decidable. We assume here that reals are represented in a standard way, so that we can compute limits of sequences of reals which are computably Cauchy.

Recall that a sequence $$(a_n)_n$$ is computably Cauchy if there is a computable map $$f$$ such that, given any $$k$$ we have $$|a_{m} - a_{n}| < 2^{-k}$$ for all $$m, n \geq f(k)$$. The standard representations of reals are like that, for example the one where a real is represented by a machine that computes an arbitrarily good rational approximation. (We can also speak in terms of computing digits, but then we have to allow negative digits. This is a well known issue in computability theory of the reals.)

Theorem: Suppose $$S \subseteq \mathbb{R}$$ is a subset such that there exists a computable sequence $$(a_n)_n$$ which is computably Cauchy and its limit $$x = \lim_n a_n$$ is outside $$S$$. Then the question "is a real number $$x$$ an element of $$S$$" is undecidable.

Proof. Suppose $$S$$ were decidable. Given any Turing machine $$T$$, consider the sequence $$b_n$$ defined as $$b_n = \begin{cases} a_n & \text{if T has not halted in the first n steps,}\\\\ a_m & \text{if T has halted in step m and m \leq n.} \end{cases}$$ It is easy to check that $$b_n$$ is computably Cauchy, therefore we can compute its limit $$y = \lim_n b_n$$. Now we have $$y \in S$$ iff $$T$$ halts, so we can solve the Halting Problem. QED.

There is a dual theorem in which we assume the sequence is outside $$S$$ but its limit is in $$S$$.

Examples of sets $$S$$ satisfying these conditions are: an open interval, a closed interval, the negative numbers, the singleton $$\lbrace 0 \rbrace$$, rational numbers, irrational numbers, transcedental numbers, algebraic numbers, etc.

A set which does not satisfy the conditions of the theorem is $$S = \lbrace q + \alpha \mid q \in \mathbb{Q}\rbrace$$ of rational numbers translated by a non-computable number $$\alpha$$. Exercise: is $$S$$ decidable?

• Thanks for your reply. Just a clarification, does the theorem say that if the set S has at least one limit point outside S, then deciding whether an element x is in S undecidable ? Then, I am a bit confused about the closed interval in the examples. Commented Mar 2, 2012 at 12:13
• The closed interval follows by the dual theorem in which you take a sequence outside $S$ whose limit is in $S$. Commented Mar 2, 2012 at 18:11
• What does it mean for $x$ to be "outside $S$ computably" (as opposed to "outside $S\hspace{.01 in}$")$\:$? $\;\;$
– user6973
Commented Mar 2, 2012 at 20:02
• That was a typo. I fidex it, thanks for noticing. Otherwise, "$x$ is computably outside $S$" might mean something like "for every $y \in S$ we may compute a positive rational $q$ such that $d(x,y) > q$", i.e., the statement "$\forall y \in S . \exists q \in \mathbb{Q} . 0 < q < d(x,y)$" is realized. But if you believe in Markov principle, then you can reconstruct such a map by just knowing that $x$ is not in $S$, so in this case there is no difference between "outside $S$ and "computably outside $S$". Commented Mar 3, 2012 at 6:52

Given a Turing machine $M$, define a Turing machine $M'$ representing a number as follows: On input $i$ run $M$ for $i$ steps on the empty input. If $M$ halted, output $0$. Otherwise output the $i$th bit of $\pi$.

The set of transcendentals is not open in $\mathbf R$ (in particular, it is dense and codense in $\mathbf R$. Hence it is undecidable.

• The set of computable real numbers is not open in $\mathbf{R}$ (in particular, it is dense and codense in $\mathbf{R}$), but it is decidable. $\:$
– user6973
Commented Mar 2, 2012 at 19:59
• Ricky, this is not true. Given an oracle for a real number, you cannot determine if it is computable or not. Commented Mar 3, 2012 at 23:06
• The set I gave is decidable, by the algorithm that always answers "Yes". $\:$ Your second sentence shows that the set I gave is not type-two decidable. $\;\;$
– user6973
Commented Mar 3, 2012 at 23:20
• @Ricky Demer: The set of computable real numbers is undecidable in two senses: (1) given an arbitrary index $e \in \mathbb{N}$, decide whether $e$ is the index of a Turing machine that computes a computable real. (2) given an arbitrary quickly-converging Cauchy sequence, determine whether it is a computable sequence. There is no common sense in which the set of computable real numbers is decidable. Commented Mar 14, 2012 at 21:17
• @Carl: There is an algorithm to given an index $\: e\in \mathbb{N} \:$ that is the index of a Turing machine that computes a computable real, decide whether $e$ is the index of a Turing machine that computes $\hspace{.1 in}$ a computable real. $\;\;$ This is the only interesting sense of decidability of sets of reals, because $\hspace{.2 in}$ your (1) is satisfied exactly by sets with no computable reals $\hspace{2.2 in}$ and your (2) is satisfied exactly by $\: \{\} \:$ and $\mathbf{R}$. $\;\;\;$
– user6973
Commented Mar 17, 2012 at 23:54

As a (hopefully fun) exercise, we show that the problem is complete for $$\Pi_2$$ (under many-one reductions). That is, equivalent to determining whether a given TM halts on all inputs. (This is strictly harder than the halting problem.)

Let $$x$$ be a given computable number (encoded as defined in the post).

Lemma 1. The problem of determining whether $$x$$ is transcendental is complete for $$\Pi_2$$.

The proof builds on this answer, which shows that determining whether a computable number is rational is $$\Sigma_2$$-complete.

Per OP, a computable number $$x$$ is encoded as a TM $$B$$ that enumerates the bits of (the fractional part) of $$x$$ in order. Specifically, letting $$B_i$$ denote the $$i$$th bit enumerated by $$B$$, the number encoded by $$B$$ is $$x(B) = \sum_{i=1}^\infty B_i\,2^{-i}$$. (For ease of presentation, we restrict to numbers $$x\in [0, 1]$$.)

Let $$A$$ denote the problem of determining whether $$x(B)$$ is algebraic, given (the encoding of) $$B$$. Any number is transcendental iff it is not algebraic. Let $$\overline A$$ denote OP's problem, of determining whether $$x(B)$$ is transcendental.

#### Hardness result: $$\overline A$$ is $$\Pi_2$$-hard

We show this by reducing the following problem to $$A$$ (the complement of $$\overline A$$).

Problem $$F$$ (for "finite"). Given (the encoding of) a TM $$M$$ that enumerates a sequence of bits, is $$\sum_i M_i$$ (where $$M_i$$ is the $$i$$th bit enumerated by $$M$$) finite?

Problem $$F$$ is easily shown to be $$\Sigma_2$$-hard. (For a proof, see Claim 1 of this answer.)

Given an input $$M$$ for $$F$$, the reduction will produce a TM $$B$$ such that $$x(B) = \displaystyle\sum_{j=1}^\infty M_j\, 2^{-j!}.$$ Specifically, the TM $$B$$ enumerates the desired bit sequence as follows:

TM $$B$$:

1. for $$i\gets 1, 2, \ldots,$$ do:
2. $$~~~$$ if $$i = j!$$ for some integer $$j$$, output $$M_j$$, else output 0

To show that the reduction is correct, we show the following claim:

Claim 1. $$\langle M \rangle \in F$$ iff $$\langle B\rangle \in A$$.

If $$M$$ outputs finitely many ones, then $$B$$ does as well, so $$x(B)$$, being the sum of finitely many rationals, is rational. This shows the forward direction of the claim. We show the converse as follows.

NB: This part is adapted almost verbatim from a related argument by Yuval Filmus.

Assume for contradiction that $$\langle M \rangle \not\in F$$ (that is, $$\sum_i M_i = \infty$$) but $$x(B)$$ is algebraic. Since the binary representation of $$x(B)$$ is aperiodic, $$x(B)$$ is also irrational, and we can apply Liouville's criterion with $$\alpha=x(B)$$:

Lemma. Suppose $$\alpha$$ is an irrational algebraic number. There exist integers $$C,n$$ such that for all integers $$p/q$$, $$\left| \alpha - \frac{p}{q} \right| \geq \frac{C}{q^n}.$$ For a proof see e.g. Wikipedia.

Fix such a $$C$$ and $$n$$ from the lemma, for $$\alpha=x(B)$$. Let $$r$$ be an arbitrarily large integer, $$r \gg n$$. Taking $$q=2^{r!}$$, by the lemma, we have $$\frac{C}{2^{r!n}} \le \left| X(B) - \frac{\sum_{i=1}^r M_i 2^{r!-i!}}{2^{r!}} \right| = O\left(\sum_{i=r+1}^\infty 2^{-i!}\right) = O\left(\frac{1}{2^{(r+1)!}}\right) = o\left(\frac{1}{2^{r!n}}\right)$$ (as $$r\to\infty$$). This is a contradiction. Hence, $$\langle M \rangle \in F$$. This completes the proof of Claim 1. So $$A$$ is $$\Sigma_2$$-hard. It follows that its complement $$\overline A$$ is $$\Pi_2$$-hard.

#### Upper bound: $$\overline A$$ is in $$\Pi_2$$

To show this we will show the equivalent statement that $$A$$ is in $$\Sigma_2$$.

Given a computable number $$x(B)$$, define $$x_u(B) = \sum_{i=1}^u B_i 2^{-i}$$, so that $$x(B) = \lim_{u\to \infty} x_u(B)$$.

Given also a polynomial $$p$$, for $$m\ge 1$$, let $$N(p, m)$$ be computed as follows:

1. Compute a bounded interval that $$x(B)$$ lies in. (By our definition of computable number, we can take this interval to be $$[0,1]$$, but this step should be possible with any reasonable definition.)

2. Compute a finite upper bound $$D$$ on the absolute value of the derivative of $$p$$ within the bounded interval. (E.g., assuming the interval lies in $$[-X, X]$$ and $$p(x) = \sum_{i=0}^d p_i x^i$$, take $$D = \sum_{i=0}^d |i p_i X^{i-1}|$$.)

3. Finally, take $$N(p, m)$$ just large enough so that $$D/2^{N(p, m)} \le 1/m$$.

Note that by the choice of $$D$$, we have (for all $$p\in P, m\ge 1$$) $$~~ |p(x_{N(p,m)}(B)) - p(x(B))| \le D|x(B) - x_{N(p,m)}(B)| \le D/2^{N(p, m)} \le 1/m. ~~(1)$$

Let $$P$$ be the set of single-variable polynomials with integer coefficients.

Claim 2. $$x(B)$$ is algebraic if and only if $$~~~~~~~~~~~~~~~~~~~~~~~~~ (\exists p\in P)~(\forall m\ge 1)~|p(x_{N(p,m)}(B))| \le 1/m. ~~~~~~~~~~~~~~~~~~~~~~~~~(2)$$

To finish we prove the claim. (The claim implies that $$A$$ is in $$\Sigma_2$$, because $$p(x_{N(p,m)}(B))$$ is computable given $$B$$, $$p$$ and $$m$$.)

Now suppose that $$x(B)$$ is algebraic, that is, $$p(x(B)) = 0$$ for some $$p$$ in $$P$$. Then (2) holds because, for this $$p$$ and all $$m\ge 1$$, by (1), $$|p(x_{N(p,m)}(B))-0| \le 1/m.$$

Conversely, suppose (2) holds. Then for some $$p\in P$$, by (1) and then (2),

$$(\forall m\ge 1)~~|p(x(B))| \le |p(x_{N(p,m)}(B))| + 1/m \le 2/m,$$ so $$p(x(B)) = 0$$. So $$x(B)$$ is algebraic.