<p>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.</p>
<p>Recall that a sequence <span class="math-container">$(a_n)_n$</span> is computably Cauchy if there is a computable map <span class="math-container">$f$</span> such that, given any <span class="math-container">$k$</span> we have <span class="math-container">$|a_{m} - a_{n}| &lt; 2^{-k}$</span> for all <span class="math-container">$m, n \geq f(k)$</span>. 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.)</p>
<blockquote>
<p><strong>Theorem:</strong> Suppose <span class="math-container">$S \subseteq \mathbb{R}$</span> is a subset such that there exists a <em>computable</em> sequence <span class="math-container">$(a_n)_n$</span> which is computably Cauchy and its limit <span class="math-container">$x = \lim_n a_n$</span> is outside <span class="math-container">$S$</span>. Then the question &quot;is a real number <span class="math-container">$x$</span> an element of <span class="math-container">$S$</span>&quot; is undecidable.</p>
</blockquote>
<p><em>Proof.</em>
Suppose <span class="math-container">$S$</span> were decidable. Given any Turing machine <span class="math-container">$T$</span>, consider the sequence <span class="math-container">$b_n$</span> defined as
<span class="math-container">$$b_n = \begin{cases}
a_n &amp; \text{if $T$ has not halted in the first $n$ steps,}\\\\
a_m &amp; \text{if $T$ has halted in step $m$ and $m \leq n$.}
\end{cases}$$</span>
It is easy to check that <span class="math-container">$b_n$</span> is computably Cauchy, therefore we can compute its limit <span class="math-container">$y = \lim_n b_n$</span>. Now we have <span class="math-container">$y \in S$</span> iff <span class="math-container">$T$</span> halts, so we can solve the Halting Problem. QED.</p>
<p>There is a dual theorem in which we assume the sequence is outside <span class="math-container">$S$</span> but its limit is in <span class="math-container">$S$</span>.</p>
<p>Examples of sets <span class="math-container">$S$</span> satisfying these conditions are: an open interval, a closed interval, the negative numbers, the singleton <span class="math-container">$\lbrace 0 \rbrace$</span>, rational numbers, irrational numbers, <em>transcedental numbers</em>, algebraic numbers, etc.</p>
<p>A set which does not satisfy the conditions of the theorem is <span class="math-container">$S = \lbrace q + \alpha \mid q \in \mathbb{Q}\rbrace$</span> of rational numbers translated by a <em>non-computable</em> number <span class="math-container">$\alpha$</span>. Exercise: is <span class="math-container">$S$</span> decidable?</p>

CC BY-SA 3.0
2012-03-02T12:13:44.873Z
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.
ipsofacto
CC BY-SA 3.0
2012-03-02T18:11:43.327Z
The closed interval follows by the dual theorem in which you take a sequence outside $S$ whose limit is in $S$.
Andrej Bauer
CC BY-SA 3.0
2012-03-03T06:52:35.427Z
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$".
Andrej Bauer
CC BY-SA 4.0
2012-03-02T11:31:42.130Z
2021-08-19T09:34:08.150Z
2021-08-19T09:34:08.150Z
Andrej Bauer
<p>Given a Turing machine $M$, define a Turing machine $M&#39;$ 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$.</p>

CC BY-SA 3.0
2012-03-02T09:40:02.447Z
2012-03-02T09:40:02.447Z
Kristoffer Arnsfelt Hansen
<p>The set of transcendentals is not open in $\mathbf R$ (in particular, it is dense and codense in $\mathbf R$. Hence it is undecidable.</p>

CC BY-SA 3.0
2012-03-14T21:17:37.067Z
@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.
Carl Mummert
CC BY-SA 3.0
2012-03-18T10:36:00.507Z
@Ricky Demer: The halting problem would be solvable if you could just say "given an index of a machine that halts, I can decide whether the machine halts". You have to be able to tell whether an index of an arbitrary machine computes a computable real in order for the problem I labeled (1) to be decidable. It is true that few subsets of $\mathbb{R}$ are decidable under definition (2), which is why we typically look at $2^{\omega}$ or $\omega^{\omega}$ instead. But the problem you described is not one that anyone else would describe as "the computable reals are decidable"
Carl Mummert
CC BY-SA 3.0
2012-03-03T23:06:00.943Z
Ricky, this is not true. Given an oracle for a real number, you cannot determine if it is computable or not.
David Harris
CC BY-SA 3.0
2012-03-02T13:53:16.383Z
2012-03-02T13:53:16.383Z
David Harris
<p>As a (hopefully fun) exercise, we show that the problem is complete for <span class="math-container">$\Pi_2$</span> (under many-one reductions).
That is, equivalent to determining whether a given TM halts on <em>all</em> inputs.
(This is strictly harder than the halting problem.)</p>
<p>Let <span class="math-container">$x$</span> be a given computable number (encoded as defined in the post).</p>
<p><strong>Lemma 1.</strong> <em>The problem of determining whether <span class="math-container">$x$</span> is transcendental is complete for <span class="math-container">$\Pi_2$</span>.</em></p>
<p>The proof builds on <a href="https://cstheory.stackexchange.com/a/53857/8237">this answer</a>,
which shows that determining whether a computable number is <em>rational</em> is <span class="math-container">$\Sigma_2$</span>-complete.</p>
<p>Per OP, a computable number <span class="math-container">$x$</span> is encoded as a TM <span class="math-container">$B$</span> that
enumerates the bits of (the fractional part) of <span class="math-container">$x$</span> in order.
Specifically, letting <span class="math-container">$B_i$</span> denote the <span class="math-container">$i$</span>th bit enumerated by <span class="math-container">$B$</span>,
the number encoded by <span class="math-container">$B$</span> is <span class="math-container">$x(B) = \sum_{i=1}^\infty B_i\,2^{-i}$</span>.
(For ease of presentation, we restrict to numbers <span class="math-container">$x\in [0, 1]$</span>.)</p>
<p>Let <span class="math-container">$A$</span> denote the problem of determining whether <span class="math-container">$x(B)$</span> is algebraic, given (the encoding of) <span class="math-container">$B$</span>.
Any number is transcendental iff it is not algebraic.
Let <span class="math-container">$\overline A$</span> denote OP's problem, of determining whether <span class="math-container">$x(B)$</span> is transcendental.</p>
<h4>Hardness result: <span class="math-container">$\overline A$</span> is <span class="math-container">$\Pi_2$</span>-hard</h4>
<p>We show this by reducing the following problem to <span class="math-container">$A$</span> (the complement of <span class="math-container">$\overline A$</span>).</p>
<blockquote>
<p><strong>Problem <span class="math-container">$F$</span> (for &quot;finite&quot;).</strong> <em>Given (the encoding of) a TM <span class="math-container">$M$</span> that enumerates a sequence of bits, is <span class="math-container">$\sum_i M_i$</span> (where <span class="math-container">$M_i$</span> is the <span class="math-container">$i$</span>th bit enumerated by <span class="math-container">$M$</span>) finite?</em></p>
</blockquote>
<p>Problem <span class="math-container">$F$</span> is easily shown to be <span class="math-container">$\Sigma_2$</span>-hard.
(For a proof, see Claim 1 of <a href="https://cstheory.stackexchange.com/a/53857/8237">this answer</a>.)</p>
<p>Given an input <span class="math-container">$M$</span> for <span class="math-container">$F$</span>, the reduction will produce a TM <span class="math-container">$B$</span> such that
<span class="math-container">$$x(B) = \displaystyle\sum_{j=1}^\infty M_j\, 2^{-j!}.$$</span>
Specifically, the TM <span class="math-container">$B$</span> enumerates the desired bit sequence as follows:</p>
<p>TM <span class="math-container">$B$</span>:</p>
<ol>
<li>for <span class="math-container">$i\gets 1, 2, \ldots,$</span> do:</li>
<li><span class="math-container">$~~~$</span> if <span class="math-container">$i = j!$</span> for some integer <span class="math-container">$j$</span>, output <span class="math-container">$M_j$</span>, else output 0</li>
</ol>
<p>To show that the reduction is correct, we show the following claim:</p>
<p><strong>Claim 1.</strong> <em><span class="math-container">$\langle M \rangle \in F$</span> iff <span class="math-container">$\langle B\rangle \in A$</span>.</em></p>
<p>If <span class="math-container">$M$</span> outputs finitely many ones, then <span class="math-container">$B$</span> does as well, so <span class="math-container">$x(B)$</span>, being the sum of finitely many rationals, is rational.
This shows the forward direction of the claim. We show the converse as follows.</p>
<hr />
<p><strong>NB: This part is adapted almost verbatim from <a href="https://math.stackexchange.com/a/1270670/48535">a related argument</a> by Yuval Filmus.</strong></p>
<p>Assume for contradiction that <span class="math-container">$\langle M \rangle \not\in F$</span>
(that is, <span class="math-container">$\sum_i M_i = \infty$</span>) but <span class="math-container">$x(B)$</span> is algebraic.
Since the binary representation of <span class="math-container">$x(B)$</span> is aperiodic, <span class="math-container">$x(B)$</span> is also irrational,
and we can apply Liouville's criterion with <span class="math-container">$\alpha=x(B)$</span>:</p>
<p><strong>Lemma.</strong> <em>Suppose <span class="math-container">$\alpha$</span> is an irrational algebraic number. There exist integers <span class="math-container">$C,n$</span> such that for all integers <span class="math-container">$p/q$</span>, <span class="math-container">$$\left| \alpha - \frac{p}{q} \right| \geq \frac{C}{q^n}.$$</span></em>
For a proof see e.g. <a href="https://en.wikipedia.org/wiki/Liouville_number#Liouville_numbers_and_transcendence" rel="nofollow noreferrer">Wikipedia</a>.</p>
<p>Fix such a <span class="math-container">$C$</span> and <span class="math-container">$n$</span> from the lemma, for <span class="math-container">$\alpha=x(B)$</span>.
Let <span class="math-container">$r$</span> be an arbitrarily large integer, <span class="math-container">$r \gg n$</span>.
Taking <span class="math-container">$q=2^{r!}$</span>, by the lemma, we have
<span class="math-container">$$ \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)$$</span>
(as <span class="math-container">$r\to\infty$</span>).
This is a contradiction.
Hence, <span class="math-container">$\langle M \rangle \in F$</span>.
This completes the proof of Claim 1.
So <span class="math-container">$A$</span> is <span class="math-container">$\Sigma_2$</span>-hard.  It follows that its complement <span class="math-container">$\overline A$</span> is <span class="math-container">$\Pi_2$</span>-hard.</p>
<hr />
<h4>Upper bound: <span class="math-container">$\overline A$</span> is in <span class="math-container">$\Pi_2$</span></h4>
<p>To show this we will show the equivalent statement that <span class="math-container">$A$</span> is in <span class="math-container">$\Sigma_2$</span>.</p>
<p>Given a computable number <span class="math-container">$x(B)$</span>,
define <span class="math-container">$x_u(B) = \sum_{i=1}^u B_i 2^{-i}$</span>,
so that <span class="math-container">$x(B) = \lim_{u\to \infty} x_u(B)$</span>.</p>
<p>Given also a polynomial <span class="math-container">$p$</span>, for <span class="math-container">$m\ge 1$</span>, let <span class="math-container">$N(p, m)$</span>
be computed as follows:</p>
<ol>
<li><p>Compute a bounded interval that <span class="math-container">$x(B)$</span> lies in.
(By our definition of computable number, we can take this interval to be <span class="math-container">$[0,1]$</span>, but this step should be possible with any reasonable definition.)</p>
</li>
<li><p>Compute a finite upper bound <span class="math-container">$D$</span> on the absolute value of the derivative of <span class="math-container">$p$</span> within the bounded interval.  (E.g., assuming the interval lies in <span class="math-container">$[-X, X]$</span> and <span class="math-container">$p(x) = \sum_{i=0}^d p_i x^i$</span>, take <span class="math-container">$D = \sum_{i=0}^d |i p_i X^{i-1}|$</span>.)</p>
</li>
<li><p>Finally, take <span class="math-container">$N(p, m)$</span> just large enough so that <span class="math-container">$D/2^{N(p, m)} \le 1/m$</span>.</p>
</li>
</ol>
<p>Note that by the choice of <span class="math-container">$D$</span>, we have (for all <span class="math-container">$p\in P, m\ge 1$</span>)
<span class="math-container">$$
~~
|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)$$</span></p>
<p>Let <span class="math-container">$P$</span> be the set of single-variable polynomials with integer coefficients.</p>
<p><strong>Claim 2.</strong> <em><span class="math-container">$x(B)$</span> is algebraic if and only if</em>
<span class="math-container">$$
~~~~~~~~~~~~~~~~~~~~~~~~~
(\exists p\in P)~(\forall m\ge 1)~|p(x_{N(p,m)}(B))| \le 1/m.
~~~~~~~~~~~~~~~~~~~~~~~~~(2)$$</span></p>
<p>To finish we prove the claim.
(The claim implies that <span class="math-container">$A$</span> is in <span class="math-container">$\Sigma_2$</span>,
because <span class="math-container">$p(x_{N(p,m)}(B))$</span> is computable given <span class="math-container">$B$</span>, <span class="math-container">$p$</span> and <span class="math-container">$m$</span>.)</p>
<p>Now suppose that <span class="math-container">$x(B)$</span> is algebraic,
that is, <span class="math-container">$p(x(B)) = 0$</span> for some <span class="math-container">$p$</span> in <span class="math-container">$P$</span>.
Then (2) holds because, for this <span class="math-container">$p$</span> and all <span class="math-container">$m\ge 1$</span>, by (1),
<span class="math-container">$$|p(x_{N(p,m)}(B))-0| \le 1/m.$$</span></p>
<p>Conversely, suppose (2) holds.
Then for some <span class="math-container">$p\in P$</span>, by (1) and then (2),</p>
<p><span class="math-container">$$(\forall m\ge 1)~~|p(x(B))| \le |p(x_{N(p,m)}(B))| + 1/m \le 2/m,$$</span>
so <span class="math-container">$p(x(B)) = 0$</span>.  So <span class="math-container">$x(B)$</span> is algebraic.</p>

CC BY-SA 4.0
2024-02-05T20:06:47.533Z
2024-02-05T20:26:34.597Z
2024-02-05T20:26:34.597Z
Neal Young
<p>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.</p>

<p>My question is whether it is known that deciding whether a number is transcendental is undecidable. </p>

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

CC BY-SA 3.0
2012-03-02T16:32:25.773Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-08-12T08:29:19.743Z
My opinion is that transcendence should be decidable.
Here a sketch of my "proof", based on the fact that integer coefficient polynomials are countable:
https://math.stackexchange.com/questions/4222372/transcendental-numbers-are-decidable-a-proof
giorgiomugnaini
CC BY-SA 4.0
2021-08-12T08:32:12.093Z
But IMHO, your question includes two DIFFERENT sub-questions:
* transcendence of a given number is decidable?
* transcendence of a given number is computable?
giorgiomugnaini
CC BY-SA 4.0
2024-02-04T18:38:41.303Z
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. https://cstheory.stackexchange.com/a/53857/8237 .
Neal Young
<computability><decidability><computable-analysis>
Decidability of transcendental numbers
ipsofacto
# Decidability of transcendental numbers

(Asked by: username_0 on 2012-03-02)

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.

**Tags:** computability, decidability, computable-analysis
> **Comments:**
> **username_1**: 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.  
> **username_2**: My opinion is that transcendence should be decidable. Here a sketch of my "proof", based on the fact that integer coefficient polynomials are countable: https://math.stackexchange.com/questions/4222372/transcendental-numbers-are-decidable-a-proof  
> **username_2**: But IMHO, your question includes two DIFFERENT sub-questions: * transcendence of a given number is decidable? * transcendence of a given number is computable?  
> **username_3**: 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. https://cstheory.stackexchange.com/a/53857/8237 .  

---

## 4 answers

### Answer by username_4 on 2012-03-02. Score: 12

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?

> **Comments:**
> **username_0**: 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.  
> **username_4**: The closed interval follows by the dual theorem in which you take a sequence outside $S$ whose limit is in $S$.  
> **username_4**: 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$".  

---

### Answer by username_5 on 2012-03-02. Score: 5

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 by username_6 on 2012-03-02. Score: 1

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

> **Comments:**
> **username_6**: Ricky, this is not true. Given an oracle for a real number, you cannot determine if it is computable or not.  
> **username_7**: @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.  
> **username_7**: @Ricky Demer: The halting problem would be solvable if you could just say "given an index of a machine that halts, I can decide whether the machine halts". You have to be able to tell whether an index of an arbitrary machine computes a computable real in order for the problem I labeled (1) to be decidable. It is true that few subsets of $\mathbb{R}$ are decidable under definition (2), which is why we typically look at $2^{\omega}$ or $\omega^{\omega}$ instead. But the problem you described is not one that anyone else would describe as "the computable reals are decidable"  

---

### Answer by username_3 on 2024-02-05. Score: 0

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](https://cstheory.stackexchange.com/a/53857/8237),
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](https://cstheory.stackexchange.com/a/53857/8237).)

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](https://math.stackexchange.com/a/1270670/48535) 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](https://en.wikipedia.org/wiki/Liouville_number#Liouville_numbers_and_transcendence).

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.


---

