Decidability of transcendental numbers

Question

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.

Answer 1

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?

Answer 2

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

Answer 3

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

Answer 4

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.