8
$\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$

Your Answer

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

Browse other questions tagged or ask your own question.