Let $R$ be a ring such that all of its elements have a finite number of divisors, ie $\forall r\in R\, |\{x\in R: x|r\}|<\infty$.
Then we can decide whether a polynomial in $R[t]$ is reducible through [Kronecker's method](https://www.encyclopediaofmath.org/index.php/Kronecker_method).


Even in the ring $\mathbb{Q}[x,\sqrt{x},\sqrt[4]{x},...]$, where $x$ has an infinite number of divisors, it is easy to list any polynomial's possible factors, and reducibility is decidable.


Is there a ring for which the reducibility of a polynomial is undecidable?


Is there a countable ring with computable ring operations and decidable equality for which the reducibility of a polynomial is undecidable?



Is there a ring for which the reducibility of a polynomial is undecidable?
Yes, but the answer is a bit unsatisfying. This answer is a summary of the very nice paper [Computable Fields and Galois Theory](https://qcpages.qc.cuny.edu/%7Ermiller/Notices.pdf), Russel Miller, *Notices of the AMS*, 2008.


First of all, if one could not even compute with the elements of the ring $R$ at all, it would be unclear what it would mean for factorization to be computable. The usual solution is to talk about "computable rings", meaning a countable (or finite) ring $R$ where the elements are indexed by integers and the operations of addition and multiplication are given by computable functions.


The following is an example of a computable field in which factorization is not decidable: Let $p\_n$ be the $n$-th prime and let $T\_n$ be the $n$-th Turing machine and let $K = \mathbb{Q}(\sqrt{p\_n} \ : \ T\_n \ \mbox{halts})$. Given any element $\theta$ of $K$, there is a finite expression which witnesses that $\theta$ is in $K$: namely, the algebraic expression for $\theta$ in terms of finitely many $p\_n$'s and a transcript of the ruunning of the corresponding Turing machines. This can be made into a proof that $K$ is computable, in particular (in response to Matt F.'s comment) there is no issue with testing equality. However, $x^2 - p\_n$ is reducible iff $T\_n$ halts, so we cannot test reducibility.


The fields one normally meets in life do not have this issue. Reducibility is computable over $\mathbb{Q}$, $\mathbb{R} \cap \mathbb{Q}^{\mathrm{alg}}$ and over finite fields. If reducibility is computable over $k$, then it is computable over $k(t)$ and over $k[t]/f(t)$ for $f$ irreducible. That already covers the most obvious fields you know.


Searching for "computable fields" turns up a fair bit of recent research.


