<p>The answer is <strong>no</strong>; interestingly, the problem is harder to <em>state</em> satisfactorily in my opinion than it is to resolve! Roughly speaking, the subtlety which complicates the posing of the problem is that the &quot;context of computation&quot; is <strong>more complicated than</strong> the distinctions we want to make. Below I'll refer frequently to the <a href="https://en.wikipedia.org/wiki/Arithmetical_hierarchy" rel="nofollow noreferrer">arithmetical hierarchy</a>, and focus on the following three sets of natural numbers in particular:</p>
<ul>
<li><p>The set <span class="math-container">$R$</span> of indices of Turing machines which &quot;code&quot; a real number.</p>
</li>
<li><p>The set <span class="math-container">$Z$</span> of indices of Turing machines which &quot;code&quot; the real number <span class="math-container">$0$</span>. (This is what we want to use as an oracle; note that <span class="math-container">$Z\subset R$</span>.)</p>
</li>
<li><p>The set <span class="math-container">$T$</span> of indices of Turing machines which &quot;code&quot; a <em>transcendental</em> number (for simplicity I'm looking at the &quot;<span class="math-container">$n=1$</span> slice&quot; of the actual set you're interested in).</p>
</li>
</ul>
<hr />
<p>Here's the above-mentioned subtlety: each of these three sets, including the &quot;background context&quot; set <span class="math-container">$R$</span>, is <span class="math-container">$\Pi^0_2$</span>-complete. In particular, all three sets are Turing- <em>(indeed, many-one-)</em><span class="math-container">${}$</span>equivalent, and live at a significantly higher level of complexity than the intuitive (&quot;zero-testing&quot;) gap between <span class="math-container">$R$</span> and <span class="math-container">$Z$</span>, namely the halting problem. This means that &quot;<span class="math-container">$T$</span> is computable relative to <span class="math-container">$Z$</span>&quot; is technically true but feels wrong somehow.</p>
<p>So we have a methodological question to address:</p>
<h2>How can the question in the OP be made precise while blocking this sort of trivial response?</h2>
<p><em>(Incidentally a similar issue, albeit &quot;higher up,&quot; occurs in <a href="https://www.jstor.org/stable/421157" rel="nofollow noreferrer">the context of computing general antiderivatives</a> - look for the phrase &quot;hyperarithmetic <strong>in the codes</strong>.&quot; In this setting &quot;the codes&quot; is a <span class="math-container">$\Pi^1_1$</span>-complete set, while hyperarithmeticity is <span class="math-container">$\Delta^1_1$</span>.)</em></p>
<p>One natural approach is to shift from the usual picture of oracles as <em>total</em> objects to <em>partial</em> oracles. This would let us distinguish for example between the characteristic function of <span class="math-container">$Z$</span>, which is a very powerful object, and the <em>partial</em> function <span class="math-container">$$Z_R:\mathbb{N}\rightarrow\mathbb{N}:x\mapsto\begin{cases}
1 &amp; \mbox{ if } x\in Z,\\
0 &amp; \mbox{ if } x\in R\setminus Z,\\
\uparrow &amp; \mbox{ if }x\not\in R.\\
\end{cases}$$</span> which should be rather weaker. A similar distinction would exist between &quot;total <span class="math-container">$T$</span>&quot; and <span class="math-container">$T_R$</span>, and we would be interested in gauging the complexity of <span class="math-container">$T_R$</span> relative to <span class="math-container">$Z_R$</span>.</p>
<p>Unfortunately it takes some care to get computation relative to partial objects to work properly. While in my opinion this effort is very much worthwhile, in this case I'll take a simpler approach - basically, throw Venn diagrams on everything and hope for the best!</p>
<hr />
<p>We can rephrase the OP's motivating observation as saying that while both <span class="math-container">$R$</span> and <span class="math-container">$Z$</span> are <span class="math-container">$\Pi^0_2$</span>-complete, <span class="math-container">$Z$</span> &quot;sits inside&quot; <span class="math-container">$R$</span> in a noticeably <span class="math-container">$\Pi^0_1$</span>-complete way: there is a <span class="math-container">$\Pi^0_1$</span>-complete set <span class="math-container">$\hat{Z}$</span> such that <span class="math-container">$Z=R\cap\hat{Z}$</span>, and this is optimal in the sense that there is no <span class="math-container">$\Sigma^0_1$</span> (let alone computable) set <span class="math-container">$A$</span> such that <span class="math-container">$Z=R\cap A$</span>. We can ask whether <span class="math-container">$T$</span> is similarly &quot;nontrivially simple&quot; in terms of how it fits inside <span class="math-container">$R$</span>.</p>
<p>At this point a bit of terminology is in order. Sadly I don't think there is a standard terminology for this sort of thing, but the following matches what I've heard in some informal conversations:</p>
<blockquote>
<p>For a complexity class <span class="math-container">$\Gamma$</span> <em>(especially a class in the arithmetical hierarchy)</em> and a set <span class="math-container">$X$</span>, say that a set <span class="math-container">$Y$</span> <strong>is <span class="math-container">$\Gamma$</span> on <span class="math-container">$X$</span></strong>, or <span class="math-container">$Y\in\Gamma_{\cap X}$</span>, iff there is some <span class="math-container">$A\in\Gamma$</span> with <span class="math-container">$Y=X\cap A$</span>.</p>
</blockquote>
<p>My point, then, is that the question in the OP can be faithfully precisiated as:</p>
<blockquote>
<p>For which arithmetical classes <span class="math-container">$\Gamma$</span> is <span class="math-container">$T\in\Gamma_{\cap R}$</span>?</p>
</blockquote>
<p><em>(Incidentally, note that in general - letting <span class="math-container">$\check{\Gamma}$</span> be the set of sets whose complements are in <span class="math-container">$\Gamma$</span>  we have <span class="math-container">$\Gamma_{\cap X}\cap\check{\Gamma}_{\cap X}\supsetneq(\Gamma\cap\check{\Gamma})_{\cap X}$</span>.)</em></p>
<p>For example, the slightly-informal observation in the OP that <span class="math-container">$T$</span> becomes co-enumerable once we have an oracle for <span class="math-container">$Z$</span> corresponds to the fact that <span class="math-container">$T\in\Pi^0_{2\cap R}$</span> (since &quot;co-enumerable in <span class="math-container">$\Pi^0_1$</span>&quot; = <span class="math-container">$\Pi^0_2$</span>), and optimality of this bound would correspond to <span class="math-container">$T\color{red}{\not\in}\Sigma^0_{2\cap R}$</span>. That this holds is a consequence of the following:</p>
<blockquote>
<p>Not only is <span class="math-container">$T$</span> <span class="math-container">$\Pi^0_2$</span>-complete in the usual sense, it is &quot;<span class="math-container">$\Pi^0_2$</span>-complete within <span class="math-container">$R$</span>:&quot; for every <span class="math-container">$A\in\Pi^0_2$</span> there is a total computable <span class="math-container">$f$</span> which is an <span class="math-container">$m$</span>-reduction of <span class="math-container">$A$</span> to <span class="math-container">$T$</span> <strong>and</strong> has range <span class="math-container">$\subseteq R$</span>.</p>
</blockquote>
<p>This isn't hard to prove; basically, given a <span class="math-container">$\Pi^0_2$</span> property <span class="math-container">$\varphi$</span> and an input <span class="math-container">$n$</span>, build a number whose binary expansion consists of:</p>
<ul>
<li><p>a block of <span class="math-container">$0$</span>s which keeps going until (if ever) we see that <span class="math-container">$0$</span> is not a witness to <span class="math-container">$\varphi(n)$</span>, then the string <span class="math-container">$01^{2^0}0$</span>,</p>
</li>
<li><p>then a block of <span class="math-container">$0$</span>s which keeps going until (if ever) we see that <span class="math-container">$1$</span> is not a witness to <span class="math-container">$\varphi(n)$</span>, then the string <span class="math-container">$01^{2^1}0$</span>,</p>
</li>
<li><p>then a block of <span class="math-container">$0$</span>s which keeps going until (if ever) we see that <span class="math-container">$2$</span> is not a witness to <span class="math-container">$\varphi(n)$</span>, then the string <span class="math-container">$01^{2^2}0$</span>,</p>
</li>
<li><p>and so on.</p>
</li>
</ul>
<p>The resulting number is a dyadic rational iff <span class="math-container">$\varphi(n)$</span> holds, and is otherwise transcendental <a href="https://en.wikipedia.org/wiki/Liouville_number" rel="nofollow noreferrer">for Liouville-flavored reasons</a> (possibly after fixing any silly arithmetic errors I've made in the above :P).</p>

CC BY-SA 4.0
2021-10-11T06:20:17.887Z
Nice answer! Thanks. By now I don't even have a vague memory of why I was interested in this question, but still - great to have an answer! :)
Shaull
CC BY-SA 4.0
2024-03-20T01:20:46.673Z
What do you mean by “The resulting number is a dyadic rational iff φ(n)
 holds”?  what is $\phi (x)$? It's definition?
XL _At_Here_There
CC BY-SA 4.0
2024-03-20T01:33:09.063Z
@XL_At_Here_There $\varphi$ is an arbitrary $\Pi^0_2$ property; see the sentence beginning "this isn't hard to prove." (And look in Soare's book if you're not familiar with $\Pi^0_2$ completeness proofs.)
Noah Schweber
CC BY-SA 4.0
2024-03-20T02:18:46.290Z
@NoahSchweber, thanks.
XL _At_Here_There
CC BY-SA 4.0
2024-03-22T12:54:00.760Z
@NoahSchweber,  by what theorem, it can be deduced that "The resulting number is a dyadic rational iff $\varphi(n)$
 holds"?
XL _At_Here_There
CC BY-SA 4.0
2021-10-10T23:17:01.853Z
2021-10-13T21:36:37.067Z
2021-10-13T21:36:37.067Z
Noah Schweber
<p>Consider numbers $x_1,...,x_n\in \mathbb{R}$ given by TMs $M_1,...,M_n$ such that $M_i$ approximates $x_i$ to an arbitrary precision (by allowing it to run longer and longer).</p>

<p>I am interested in the following problem:</p>

<blockquote>
  <p>Decide whether $x_1,...,x_n$ are algebraically independent.</p>
</blockquote>

<p>Clearly this is undecidable, since even deciding whether $x_i=0$ is undecidable. However, if we are given an oracle to the problem of deciding whether $x_i=0$, then the above problem becomes <em>recognizable</em>: enumerate all polynomials with integer coefficients (e.g. in minlex order), and for each polynomial $p$ compute a TM $M_p$ that approximates $p(x_1,...,x_n)$ arbitrarily. Then, use the oracle to check if this number is $0$.</p>

<p>So the question is:</p>

<blockquote>
  <p>Is the problem also decidable under a zero-test oracle? i.e. is it co-recognizable?</p>
</blockquote>

<p>Remarks:</p>

<ol>
<li><p>This question relates (but is not directly connected/reducible to) my question <a href="https://cstheory.stackexchange.com/questions/32451/is-algebraic-dependency-decidable">here</a>.</p></li>
<li><p>I see that a lot of questions regarding real-numbers encounter issues with encoding. I think the encoding here is well defined (comment if I'm wrong, and I'll revise). Note that not all numbers are of course representable in this model.</p></li>
</ol>

<oracles><decidability><undecidability>
Oracle-Decidability of Algebraic Independence
Shaull
# Oracle-Decidability of Algebraic Independence

(Asked by: username_0 on 2015-12-20)

Consider numbers $x\_1,...,x\_n\in \mathbb{R}$ given by TMs $M\_1,...,M\_n$ such that $M\_i$ approximates $x\_i$ to an arbitrary precision (by allowing it to run longer and longer).

I am interested in the following problem:

> Decide whether $x\_1,...,x\_n$ are algebraically independent.

Clearly this is undecidable, since even deciding whether $x\_i=0$ is undecidable. However, if we are given an oracle to the problem of deciding whether $x\_i=0$, then the above problem becomes *recognizable*: enumerate all polynomials with integer coefficients (e.g. in minlex order), and for each polynomial $p$ compute a TM $M\_p$ that approximates $p(x\_1,...,x\_n)$ arbitrarily. Then, use the oracle to check if this number is $0$.

So the question is:

> Is the problem also decidable under a zero-test oracle? i.e. is it co-recognizable?

Remarks:

1. This question relates (but is not directly connected/reducible to) my question [here](https://cstheory.stackexchange.com/questions/32451/is-algebraic-dependency-decidable).
2. I see that a lot of questions regarding real-numbers encounter issues with encoding. I think the encoding here is well defined (comment if I'm wrong, and I'll revise). Note that not all numbers are of course representable in this model.

**Tags:** oracles, decidability, undecidability


---

## 1 answers

### Answer by username_1 on 2021-10-10. Score: 5 | Accepted answer

The answer is **no**; interestingly, the problem is harder to *state* satisfactorily in my opinion than it is to resolve! Roughly speaking, the subtlety which complicates the posing of the problem is that the "context of computation" is **more complicated than** the distinctions we want to make. Below I'll refer frequently to the [arithmetical hierarchy](https://en.wikipedia.org/wiki/Arithmetical_hierarchy), and focus on the following three sets of natural numbers in particular:

* The set $R$ of indices of Turing machines which "code" a real number.
* The set $Z$ of indices of Turing machines which "code" the real number $0$. (This is what we want to use as an oracle; note that $Z\subset R$.)
* The set $T$ of indices of Turing machines which "code" a *transcendental* number (for simplicity I'm looking at the "$n=1$ slice" of the actual set you're interested in).

---

Here's the above-mentioned subtlety: each of these three sets, including the "background context" set $R$, is $\Pi^0\_2$-complete. In particular, all three sets are Turing- *(indeed, many-one-)*${}$equivalent, and live at a significantly higher level of complexity than the intuitive ("zero-testing") gap between $R$ and $Z$, namely the halting problem. This means that "$T$ is computable relative to $Z$" is technically true but feels wrong somehow.

So we have a methodological question to address:

## How can the question in the OP be made precise while blocking this sort of trivial response?

*(Incidentally a similar issue, albeit "higher up," occurs in [the context of computing general antiderivatives](https://www.jstor.org/stable/421157) - look for the phrase "hyperarithmetic **in the codes**." In this setting "the codes" is a $\Pi^1\_1$-complete set, while hyperarithmeticity is $\Delta^1\_1$.)*

One natural approach is to shift from the usual picture of oracles as *total* objects to *partial* oracles. This would let us distinguish for example between the characteristic function of $Z$, which is a very powerful object, and the *partial* function $$Z\_R:\mathbb{N}\rightarrow\mathbb{N}:x\mapsto\begin{cases}
1 & \mbox{ if } x\in Z,\\
0 & \mbox{ if } x\in R\setminus Z,\\
\uparrow & \mbox{ if }x\not\in R.\\
\end{cases}$$ which should be rather weaker. A similar distinction would exist between "total $T$" and $T\_R$, and we would be interested in gauging the complexity of $T\_R$ relative to $Z\_R$.

Unfortunately it takes some care to get computation relative to partial objects to work properly. While in my opinion this effort is very much worthwhile, in this case I'll take a simpler approach - basically, throw Venn diagrams on everything and hope for the best!

---

We can rephrase the OP's motivating observation as saying that while both $R$ and $Z$ are $\Pi^0\_2$-complete, $Z$ "sits inside" $R$ in a noticeably $\Pi^0\_1$-complete way: there is a $\Pi^0\_1$-complete set $\hat{Z}$ such that $Z=R\cap\hat{Z}$, and this is optimal in the sense that there is no $\Sigma^0\_1$ (let alone computable) set $A$ such that $Z=R\cap A$. We can ask whether $T$ is similarly "nontrivially simple" in terms of how it fits inside $R$.

At this point a bit of terminology is in order. Sadly I don't think there is a standard terminology for this sort of thing, but the following matches what I've heard in some informal conversations:

> For a complexity class $\Gamma$ *(especially a class in the arithmetical hierarchy)* and a set $X$, say that a set $Y$ **is $\Gamma$ on $X$**, or $Y\in\Gamma\_{\cap X}$, iff there is some $A\in\Gamma$ with $Y=X\cap A$.

My point, then, is that the question in the OP can be faithfully precisiated as:

> For which arithmetical classes $\Gamma$ is $T\in\Gamma\_{\cap R}$?

*(Incidentally, note that in general - letting $\check{\Gamma}$ be the set of sets whose complements are in $\Gamma$ we have $\Gamma\_{\cap X}\cap\check{\Gamma}\_{\cap X}\supsetneq(\Gamma\cap\check{\Gamma})\_{\cap X}$.)*

For example, the slightly-informal observation in the OP that $T$ becomes co-enumerable once we have an oracle for $Z$ corresponds to the fact that $T\in\Pi^0\_{2\cap R}$ (since "co-enumerable in $\Pi^0\_1$" = $\Pi^0\_2$), and optimality of this bound would correspond to $T\color{red}{\not\in}\Sigma^0\_{2\cap R}$. That this holds is a consequence of the following:

> Not only is $T$ $\Pi^0\_2$-complete in the usual sense, it is "$\Pi^0\_2$-complete within $R$:" for every $A\in\Pi^0\_2$ there is a total computable $f$ which is an $m$-reduction of $A$ to $T$ **and** has range $\subseteq R$.

This isn't hard to prove; basically, given a $\Pi^0\_2$ property $\varphi$ and an input $n$, build a number whose binary expansion consists of:

* a block of $0$s which keeps going until (if ever) we see that $0$ is not a witness to $\varphi(n)$, then the string $01^{2^0}0$,
* then a block of $0$s which keeps going until (if ever) we see that $1$ is not a witness to $\varphi(n)$, then the string $01^{2^1}0$,
* then a block of $0$s which keeps going until (if ever) we see that $2$ is not a witness to $\varphi(n)$, then the string $01^{2^2}0$,
* and so on.

The resulting number is a dyadic rational iff $\varphi(n)$ holds, and is otherwise transcendental [for Liouville-flavored reasons](https://en.wikipedia.org/wiki/Liouville_number) (possibly after fixing any silly arithmetic errors I've made in the above :P).

> **Comments:**
> **username_0**: Nice answer! Thanks. By now I don't even have a vague memory of why I was interested in this question, but still - great to have an answer! :)  
> **username_2**: What do you mean by “The resulting number is a dyadic rational iff φ(n)  holds”?  what is $\phi (x)$? It's definition?  
> **username_1**: @XL_At_Here_There $\varphi$ is an arbitrary $\Pi^0_2$ property; see the sentence beginning "this isn't hard to prove." (And look in Soare's book if you're not familiar with $\Pi^0_2$ completeness proofs.)  
> **username_2**: @NoahSchweber, thanks.  
> **username_2**: @NoahSchweber,  by what theorem, it can be deduced that "The resulting number is a dyadic rational iff $\varphi(n)$  holds"?  

---

