Computability Questions about Fields
Seminar Room 1, Newton Institute
AbstractMany of the concepts standard in computable model theory today trace back to the 1956 paper 'Effective Procedures in Field Theory', by Fröhlich and Shepherdson. There the authors used Turing's definition of a partial computable function to show that many procedures simply could not be carried out in an arbitrary field $F$, even assuming one knows the elements of $F$ and can compute the field operations on those elements. For example, they formalized van der Waerden's intuitive notion that it is not in general decidable whether a polynomial from $F[X]$ has a root in $F$, or whether it is reducible within the polynomial ring $F[X]$. Indeed, they showed that these two questions about polynomials (having a root, and being reducible) are equicomputable: one can be done by a Turing machine if and only if the other can. Their proof generalizes easily to show that the set of reducible polynomials and the set of polynomials with roots are during-equivalent, and Rabin capitalized on these notions in his 1960 paper investigating effective algebraic closures of fields.
In this talk we will review these notions and then present recent refinements. The result of Turing-equivalence between the two sets described above was surprising: it is readily seen that decidability of irreducibility allows one to decide whether a polynomial has a root, but the reduction in the opposite direction is by no means apparent. Fröhlich and Shepherdson gave one such reduction, while another is implicit in Rabin's paper. A third reduction, which holds provided that the computable field has a computable transcendence basis over its prime subfield, was presented by the speaker in a 2010 paper. This new one has the stronger property of being a $1$-reduction: the irreducibility of a polynomial $p\in F[X]$ is reduced to the single question of whether another polynomial $q\in F[X]$, computed effectively from $p$, has a root in $F$. In the same paper, the author constructed a computable field, algebraic over the rationals (and thus trivially having a computable transcendence basis), for which there is no $1$-reduction in the opposite direction. Therefore, the two questions are indeed of distinct degrees of difficulty, although distinguishing them requires the notion of a $1$-reduction, which is finer than Turing reducibility but nevertheless absolutely standard in computability theory. This theorem was recently strengthened by the speaker's Ph.D.\ student Rebecca Steiner, who produced a computable algebraic field in which there is not even any
wtt-reduction from having a root to being reducible. Steiner has established exactly the property necessary for such a
wtt-reduction to exist, and the result has been known to surprise algebraists as well as computable model theorists.
See PDF for full abstract.