9
$\begingroup$

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.

  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.

$\endgroup$
0

1 Answer 1

3
$\begingroup$

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, 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 - 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 (possibly after fixing any silly arithmetic errors I've made in the above :P).

$\endgroup$
1
  • $\begingroup$ 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! :) $\endgroup$
    – Shaull
    Oct 11, 2021 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.