کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4661992 1633486 2012 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Computable fields and the bounded Turing reduction
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
Computable fields and the bounded Turing reduction
چکیده انگلیسی

For a computable field F, the splitting set SF of F is the set of polynomials in F[X] which factor over F, and the root set RF of F is the set of polynomials in F[X] which have a root in F.Results of Fröhlich and Shepherdson (1956) in [3], imply that for a computable field F, the splitting set SF and the root set RF are Turing-equivalent. More recently, in Miller (2010) [5], Miller showed that for algebraic fields, if we use a finer measure, the root set actually has slightly higher complexity: for algebraic fields F, it is always the case that SF≤1RF, but there are algebraic fields F where we have RF≰1SF.Here we compare the splitting set and the root set of a computable algebraic field under a different reduction: the bounded Turing (bT) reduction. We construct a computable algebraic field for which RF≰bTSF.We also define a Rabin embedding g of a field into its algebraic closure, and for a computable algebraic field F, we compare the relative complexities of RF, SF, and g(F) under m-reducibility and under bT-reducibility.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 163, Issue 6, June 2012, Pages 730-742