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?


  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.


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.