3
Computability Questions about Fields
http://sms.cam.ac.uk/media/1208197
Miller, R (City University of New York)
Tuesday 24 January 2012, 16:0016:30
40
Computability Questions about Fields
http://sms.cam.ac.uk/media/1208197
http://rss.sms.cam.ac.uk/itunesimage/1394306.jpg

Computability Questions about Fields
ucs_sms_1200622_1208197
http://sms.cam.ac.uk/media/1208197
Computability Questions about Fields
Miller, R (City University of New York)
Tuesday 24 January 2012, 16:0016:30
Fri, 27 Jan 2012 09:39:41 +0000
Isaac Newton Institute
Miller, R
4ada85a7c163072e50e7ff4df2cf19e2
a7db4d29b29fd254900b177fc16f23aa
91965870119c3d5b8cdcf4156f094f8e
39f10bf8a46caefd6d6e84ae3f787284
8217585446e583a07283d76ace337c53
Miller, R (City University of New York)
Tuesday 24 January 2012, 16:0016:30
Miller, R (City University of New York)
Tuesday 24 January 2012, 16:0016:30
Cambridge University
2132
http://sms.cam.ac.uk/media/1208197
Computability Questions about Fields
Miller, R (City University of New York)
Tuesday 24 January 2012, 16:0016:30
Many 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 duringequivalent, 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 Turingequivalence 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 1reduction: the irreducibility of a polynomial p∈F[X] is reduced to the single question of whether another polynomial q∈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 1reduction in the opposite direction. Therefore, the two questions are indeed of distinct degrees of difficulty, although distinguishing them requires the notion of a 1reduction, 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 wttreduction from having a root to being reducible. Steiner has established exactly the property necessary for such a wttreduction to exist, and the result has been known to surprise algebraists as well as computable model theorists.
Steve Greenham
http://sms.cam.ac.uk/person/sg438
20120127T09:39:54+00:00
2132
1208197
true
16x9
false