2
$\begingroup$

Let $A$ be a ring such that all elements of $A$ are complex computable numbers. I'm interested in knowing whether the decision problem that asks, given $P\in A[X]$, if $P$ has a root in $A$ is decidable.

I know that this problem is decidable for the following rings:

  • $\mathbb{Z}$, since we can easily bound the absolute value of any root of $P\in \mathbb{Z}[X]$ ;
  • the field of fractions of a ring $A$ for which the problem is decidable, by Gauss lemma ;
  • any algebraically closed field, in particular the field of computable complex numbers ;
  • the field of computable real numbers, as a corollary of Sturm's theorem, as pointed out in this comment ;

Is there some general result on the decidability of this class of problems, maybe by making extra assumptions on $A$? Do we know if there are rings for which this decision problem is undecidable?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ $A'=\mathbb{R}$ is easily decided using Sturm's theorem and so do all the cases in the last paragraph. $\endgroup$
    – plop
    Oct 15 '20 at 2:23

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.