کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4661633 | 1633447 | 2015 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Measuring complexities of classes of structures
ترجمه فارسی عنوان
اندازه گیری پیچیدگی های کلاس های ساختارها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
منطق ریاضی
چکیده انگلیسی
How do we compare the complexities of various classes of structures? The Turing ordinal of a class of structures, introduced by Jockusch and Soare, is defined in terms of the number of jumps required for coding to be possible. The back-and-forth ordinal, introduced by Montalbán, is defined in terms of ΣαΣα-types. The back-and-forth ordinal is (roughly) bounded by the Turing ordinal. In this paper, we show that, if we do not restrict the allowable classes, the reverse inequality need not hold. Indeed, for any computable ordinals α≤βα≤β we present a class of structures with back-and-forth ordinal α and Turing ordinal β. We also present an example of a class of structures with back-and-forth ordinal 1 but no Turing ordinal.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 166, Issue 12, December 2015, Pages 1365–1381
Journal: Annals of Pure and Applied Logic - Volume 166, Issue 12, December 2015, Pages 1365–1381
نویسندگان
Barbara F. Csima, Carolyn Knoll,