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

ОглядРедагувати

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

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

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

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

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

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

  • XT X
  • XT Y означає, що YT X
  • Якщо XT Y таYT Z, тоді XT Z.

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

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

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

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

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

  • Кожна степінь Тюрінга є зліченною множиною, так як вона містить рівно   множин.
  • Існує   степенів Тюрінга.
  • Для кожного степеня a виконується чітка нерівність a < a′.
  • Для кожного степеня a, множина степенів нижче a є зліченною. Множина степенів більних за a має розмір  .

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

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

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

  • Існує мінімальний степінь. Степінь a є мінімальним, якщо a не дорівнює нулю і не існує степеня між 0 та a. Тобто відношення порядку степенів не є щільним.
  • Для кожного ненульового степеня a існує степінь b, непорівняне з a.
  • Існує множина   з попарно непорівняних степенів Тюрінга.
  • Існують пари степенів без найбільшої нижньої грані. Тобто   не є решіткою.
  • Кожна злічна, частково впорядкована множина може бути включена в степені Тюрінга.
  • Жодна нескінченна, строго зростаюча послідовність степенів не має найменшу верхню грань.

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

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

Логічні властивостіРедагувати

  • Сімпсон (1977) показав, що теорія першого порядку   на мові 〈 ≤, = 〉 або 〈 ≤, ′, =〉 є багатозначною еквівалентністю до теорії істинної арифметики другого порядку. Це показує, що структура   надзвичайно складна.
  • Шор та Сламен (1999) показали, що оператор стрибку може бути визначений через структуру першого порядку для степенів мовою 〈 ≤, =〉.

Структура р.п. степенів ТюрінгаРедагувати

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

  • (G. E. Sacks, 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 R. I. Soare, 1980) Не всі скінченні решітки можуть міститися в р.п. степенях (таким чином, аби зберігався супремум та інфімум). Наступна решітка не може міститися в р.п. степені:
 
  • (A. H. Lachlan, 1966b) TНе існує пари р.п. степенів, чиї найбільші нижні грані дорівнюють 0, а найменші верхні грані дорівнюють 0′. Цей результат неформально називається недіамантова теорема.
  • (L. A. Harrington та T. A. Slaman, див. Nies, Shore, та Slaman (1998)) Теорема першого порядку для р.п. степенів мовою 〈 0, ≤, = 〉 є багатозначною еквівалентністю до теорії справжнього першого порядку арифметики.

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

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

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

Див. такожРедагувати

ПосиланняРедагувати

Монографії (рівень бакалавра)
Монографії та дослідницькі роботи (рівень магістра)
  • 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. ISBN 3-540-12155-2
  • Odifreddi, P. G. (1989). Classical Recursion Theory. Studies in Logic and the Foundations of Mathematics 125. Amsterdam: North-Holland. ISBN 978-0-444-87295-1. MR 982269. 
  • Odifreddi, P. G. (1999). Classical recursion theory. Vol. II. Studies in Logic and the Foundations of Mathematics 143. Amsterdam: North-Holland. ISBN 978-0-444-50205-6. MR 1718169. 
  • Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1, ISBN 0-07-053522-1
  • Sacks, Gerald E. Degrees of Unsolvability (Annals of Mathematics Studies), Princeton University Press. ISBN 978-0-6910-7941-7
  • 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, ISBN 978-0-7204-2061-6.
  • Shore, R. (1993). The theories of the T, tt, and wtt r.e. degrees: undecidability and beyond. У Univ. Nac. del Sur, Bahía Blanca. Proceedings of the IX Latin American Symposium on Mathematical Logic, Part 1 (Bahía Blanca, 1992). Notas Lógica Mat. 38. с. 61–70. 
  • Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7
  • Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181. MR508451
Науково-дослідницькі роботи