В інформатиці та математичній логіці Степінь Тюрінга названа на честь Алана Тюрінга або степінь нерозв язності множини н

В інформатиці та математичній логіці Степінь Тюрінга (названа на честь Алана Тюрінга) або степінь нерозв'язності множини натуральних чисел вимірює рівень алгоритмічної нерозв'язності множини.

Огляд

Концепція степені Тюрінга є фундаментальною в теорії обчислюваності, де множини натуральних чисел зазвичай розглядаються як проблеми вибору. Степінь Тюрінга для даної множини є мірою того, наскільки важко розв'язати проблему вибору, пов'язану з множиною, тобто визначити, чи є довільне число у заданій множині.

Дві множини еквівалентні за Тюрінгом, якщо вони мають однаковий рівень нерозв'язності; кожна степінь Тюрінга є колекцією множин, еквівалентних за Тюрінгом, тож дві множини мають різні степені Тюрінга тільки тоді, коли вони не еквівалентні за Тюрінгом. Більше того, степені Тюрінга є частково впорядкованими, тож якщо степінь Тюрінга для множини X менша за степінь Тюрінга для множини Y, тоді будь-яка (необчислювана) процедура, що правильно визначає чи належить число множині Y може бути ефективно перетворена на процедуру, що вирішує, чи належить число множині X. У цьому сенсі степінь Тюрінга множини відповідає рівню її нерозв'язності.

Термін степінь Тюрінга був введений Емілем Постом (1944). Багато фундаментальних результатів у цій сфері були встановлені Стівеном Коулом Кліні та Постом (1954). Степінь Тюрінга з тих пір є областю інтенсивних наукових досліджень. Багато доведень у цій області використовують метод доведення, відомий як метод пріоритету.

Еквівалентність за Тюрінгом

Тут і нижче під терміном множина будемо розуміти множину натуральних чисел. Множина X є ^[en] для множини Y, якщо існує пророча машина Тюрінга, котра приймає рішення щодо належності до X, коли є пророцтво щодо членства у Y. Позначення X ≤_TY означає, що X скорочується за Тюрінгом до Y.

Дві множини X та Y є еквівалентними за Тюрінгом, якщо X скорочується за Тюрінгом до Y, а Y скорочується за Тюрінгом до X. Позначання X ≡_TY означає, що X та Y є еквівалентними за Тюрінгом. Відношення ≡_T може бути розглянуто як відношення еквівалентності, що означає, що для кожної множини X, Y та Z:

X ≡_TX
X ≡_TY означає, що Y ≡_TX
Якщо X ≡_TY таY ≡_TZ, тоді X ≡_TZ.

Степінь Тюрінга це клас еквівалентності відношення ≡_T. Позначення [X] означає, що клас еквівалентності містить множину X. Повна колекція степенів Тюрінга позначається як ${\mathcal {D}}$ .

Степені Тюрінга частково впорядковані ≤ це означає, що [X] ≤ [Y] тоді і тільки тоді, коли X ≤_TY. Існує унікальна степінь Тюрінга, яка містить всі обчислювані множини, і ця степінь менша, ніж будь-яка інша степінь. Вона позначається як 0 (нуль), тому що це найменший елемент частково впорядкованої множини ${\mathcal {D}}$ . (Часто для позначення степені Тюрінга використовують жирний шрифт, аби відрізнити їх від множин. Коли ніякої плутанини не може статись, як наприклад з [X], жирний шрифт не є необхідним.)

Для двох будь-яких множин X та Y, X об'єднане з Y, пишеться як X ⊕ Y, є за визначенням об'єднанням множин {2n : n ∈ X} та {2m+1 : m ∈ Y}. Степінь Тюрінга для об'єднання X ⊕ Y є степенів X та Y. Так ${\mathcal {D}}$ є . Найменша верхня грань ступенів a та b позначається як a ∪ b. Відомо, що ${\mathcal {D}}$ не є решіткою, адже там існує пари ступенів без найбільшої нижньої грані.

Для будь-якої множини X позначення X′ означає множину індексів для пророчої машини, на котрих відбудеться зупинка при використанні X як пророцтва. Множина X′ називається для X. Оператор стрибку Тюрінга для степені [X] є, за визначенням, степінь [X′]; це є валідним визначенням, тому що X′ ≡_TY′ для X ≡_TY. Ключовим прикладом є 0′, степінь для проблеми зупинки.

Основні властивості степенів Тюрінга

Кожна степінь Тюрінга є зліченною множиною, так як вона містить рівно $\aleph _{0}$ множин.
Існує $2^{\aleph _{0}}$ степенів Тюрінга.
Для кожного степеня a виконується чітка нерівність a < a′.
Для кожного степеня a, множина степенів нижче a є зліченною. Множина степенів більних за a має розмір $2^{\aleph _{0}}$ .

Структура степенів Тюрінга

Багато досліджень було присвячено структурі степенів Тюринга. Наступний список містить лише деякі з багатьох відомих результатів. Один загальний висновок, який можна зробити з досліджень, полягає в тому, що структура степенів Тюринга надзвичайно складна.

Властивості порядку

Існує мінімальний степінь. Степінь a є мінімальним, якщо a не дорівнює нулю і не існує степеня між 0 та a. Тобто відношення порядку степенів не є .
Для кожного ненульового степеня a існує степінь b, непорівняне з a.
Існує множина $2^{\aleph _{0}}$ з попарно непорівняних степенів Тюрінга.
Існують пари степенів без найбільшої нижньої грані. Тобто ${\mathcal {D}}$ не є решіткою.
Кожна злічна, частково впорядкована множина може бути включена в степені Тюрінга.
Жодна нескінченна, строго зростаюча послідовність степенів не має найменшу верхню грань.

Властивості, що включають у себе стрибок

Для кожного степеня a існує степінь, чітко розташований між a та a′. Фактично, існує злічна послідовність попарно непорівняних степенів Тюрінга між a та a′.
Степінь a має вигляд b′ тоді і тільки тоді, коли 0′ ≤ a.
Для кожного степеня a існує степінь b такий, що a < b та b′ = a′; тоді степінь b називається нижнім відносно до a.
Існує безкінечна послідовність a_i степенів, для яких a′_i+1 ≤ a_i для кожного i.

Логічні властивості

Сімпсон (1977) показав, що теорія першого порядку ${\mathcal {D}}$ на мові ⟨ ≤, = ⟩ або ⟨ ≤, ′, =⟩ є багатозначною еквівалентністю до теорії істинної арифметики другого порядку. Це показує, що структура ${\mathcal {D}}$ надзвичайно складна.
Шор та Сламен (1999) показали, що оператор стрибку може бути визначений через структуру першого порядку для степенів мовою ⟨ ≤, =⟩.

Структура рекурсивно перераховних степенів Тюрінга

Степінь називається рекурсивно перераховним, якщо він містить . Кожний рекурсивно перераховний степінь менший або рівний до 0′, але не кожен степінь, менший за 0′, є рекурсивно перераховним степенем.

(, 1964) Р.П степені є щільними; між двома р.п. степенями існує третій р.п. степінь.
(A. H. Lachlan, 1966a and C. E. M. Yates, 1966) Існує два р.п. степеня без найбільшої нижньої грані в р.п. степенях.
(A. H. Lachlan, 1966a and C. E. M. Yates, 1966) Існує пара ненульових р.п. степенів з найбільшою нижньою граню рівною 0.
(S. K. Thomason, 1971) Кожна скінченна розподілена решітка може міститися в р.п. степені. Фактично, перераховна булева алгебра може міститися таким чином, що зберігатиметься супремум та інфімум.
(A. H. Lachlan and , 1980) Не всі скінченні решітки можуть міститися в р.п. степенях (таким чином, аби зберігався супремум та інфімум). Наступна решітка не може міститися в р.п. степені:

(A. H. Lachlan, 1966b) Не існує пари р.п. степенів, чиї найбільші нижні грані дорівнюють 0, а найменші верхні грані дорівнюють 0′. Цей результат неформально називається недіамантова теорема.
( та , див. Nies, Shore, та Slaman (1998)) Теорема першого порядку для р.п. степенів мовою ⟨ 0, ≤, = ⟩ є багатозначною еквівалентністю до теорії справжнього першого порядку арифметики.

Проблема Поста та метод пріоритету

Запит «Проблема Поста» перенаправляє сюди; Проблема збіжності Поста .

Еміль Пост вивчав р.п. степінь Тюрінга і задався питанням, чи є якийсь р.п. степінь точно між 0 та 0′. Проблема побудови такого степеня (або доведення, що такого не існує) стала називатися проблемою Поста. Ця проблема була вирішена незалежно Фридбергом та у 1950-х роках. Було доведено, що ці проміжниі р.п. степені існують. Обидва їх докази використовували один і той самий новий метод побудови р.п. степенів, який отримав назву метод пріоритету. Метод пріоритету зараз є основною технікою для встановлення результатів стосовно р.п. множин.

Ідея методу пріоритету для побудови р.п. множини X полягає у переліку зліченої послідовності вимог, які X повинна задовольняти. Наприклад, щоб побудувати р.п. множину X між 0 та 0′, досить задовольнити вимогам A_e і B_e для кожного натурального числа e, де A_e вимагає, щоб пророча машина з індексом e не обчислювала 0′ з X і B_e вимагає, щоб машина Тюрінга з індексом e (і без пророцтва) не обчислювала X. Ці вимоги вводяться в пріоритетний порядок, що є явною бієкцією вимог та натуральних чисел. Доведення проходить індуктивно з одним етапом для кожного натурального числа; ці етапи можна розглядати як етапи часу, протягом яких перелічується набір X. На кожному етапі числа можуть бути або введені в X, або назавжди відхилені від вводу у X задля спроби задовольнити вимоги (тобто змусити їх триматись, коли всі X перераховано). Іноді, число можна перерахувати в X, щоб задовольнити одну вимогу, але це може призвести до того, що раніше задоволена вимога стає незадоволеною (тобто вражена). Пріоритетний порядок на вимоги використовується для визначення того, яку вимогу потрібно виконати у цьому випадку. Неформальна ідея полягає в тому, що, якщо вимога вражена, то вона в кінцевому підсумку припинить бути такою після того, як всі вимоги щодо вищого пріоритету перестануть бути враженими, хоча не кожний пріоритетний аргумент має таку властивість. Потрібно зробити зауваження, що загальна множина X є р.п. і задовольняє всім вимогам. Пріоритетні аргументи можуть бути використані для доведення багатьох фактів про р.п. множини; використовувані вимоги та спосіб, яким вони виконуються, повинні бути ретельно відібрані для отримання необхідного результату.

Див. також

Посилання

Монографії (рівень бакалавра)

Cooper, S.B. Computability theory. Chapman & Hall/CRC, Boca Raton, FL, 2004.
Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ;

Монографії та дослідницькі роботи (рівень магістра)

Ambos-Spies, K. and Fejer, P. Degrees of Unsolvability. Unpublished. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
Lerman, M. Degrees of unsolvability. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1983.
Odifreddi, P. G. (1989), Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics, т. 125, Amsterdam: North-Holland, ISBN , MR 0982269
Odifreddi, P. G. (1999), Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics, т. 143, Amsterdam: North-Holland, ISBN , MR 1718169
Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ,
Sacks, Gerald E. Degrees of Unsolvability (Annals of Mathematics Studies), Princeton University Press.
Simpson, S. Degrees of unsolvability: a survey of results. Handbook of Mathematical Logic, North-Holland, 1977, pp. 631–652.
Shoenfield, Joseph R. Degrees of Unsolvability, North-Holland/Elsevier, .
(1993), Univ. Nac. del Sur, Bahía Blanca (ред.), The theories of the T, tt, and wtt r.e. degrees: undecidability and beyond, Notas Lógica Mat., т. 38, с. 61—70
Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987.
Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181. MR508451

Науково-дослідницькі роботи

Kleene, Stephen Cole; Post, Emil L. (1954), The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics, Second Series, 59 (3): 379—407, doi:10.2307/1969708, ISSN 0003-486X, JSTOR 1969708, MR 0061078
Lachlan, A.H. (1966a), Lower Bounds for Pairs of Recursively Enumerable Degrees, Proceedings of the London Mathematical Society, 3 (1): 537, doi:10.1112/plms/s3-16.1.537.
Lachlan, A.H. (1966b), The impossibility of finding relative complements for recursively enumerable degrees, J. Symb. Logic, 31 (3): 434—454, doi:10.2307/2270459, JSTOR 2270459.
Lachlan, A.H.; Soare, R.I. (1980), Not every finite lattice is embeddable in the recursively enumerable degrees, Advances in Mathematics, 37: 78—82, doi:10.1016/0001-8708(80)90027-4.
Nies, André; Shore, Richard A.; (1998), Interpretability and definability in the recursively enumerable degrees, Proceedings of the London Mathematical Society, 77 (2): 241—291, doi:10.1112/S002461159800046X, ISSN 0024-6115, MR 1635141
Post, Emil L. (1944), Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, 50 (5): 284—316, doi:10.1090/S0002-9904-1944-08111-1, ISSN 0002-9904, MR 0010514
(1964), The recursively enumerable degrees are dense, Annals of Mathematics, Second Series, 80 (2): 300—312, doi:10.2307/1970393, JSTOR 1970393.
; (1999), Defining the Turing jump, Mathematical Research Letters, 6: 711—722, doi:10.4310/mrl.1999.v6.n6.a10, ISSN 1073-2780, MR 1739227
Simpson, Stephen G. (1977), First-order theory of the degrees of recursive unsolvability, Annals of Mathematics, Second Series, 105 (1): 121—139, doi:10.2307/1971028, ISSN 0003-486X, JSTOR 1971028, MR 0432435
Thomason, S.K. (1971), Sublattices of the recursively enumerable degrees, Z. Math. Logik Grundlag. Math., 17: 273—280, doi:10.1002/malq.19710170131.
Yates, C.E.M. (1966), A minimal pair of recursively enumerable degrees, Journal of Symbolic Logic, 31 (2): 159—168, doi:10.2307/2269807, JSTOR 2269807.