степень Тьюринга

В информатике и математической логике степень Тьюринга (названная в честь Алана Тьюринга ) или степень неразрешимости множества натуральных чисел измеряет уровень алгоритмической неразрешимости множества.

Понятие степени Тьюринга является основополагающим в теории вычислимости , где множества натуральных чисел часто рассматриваются как проблемы принятия решений . Степень Тьюринга множества является мерой того, насколько сложно решить проблему принятия решений, связанную с множеством, то есть определить, находится ли произвольное число в данном множестве.

Два множества эквивалентны по Тьюрингу , если они имеют одинаковый уровень неразрешимости; каждая степень Тьюринга представляет собой набор эквивалентных по Тьюрингу множеств, так что два множества находятся в разных степенях Тьюринга ровно тогда, когда они не эквивалентны по Тьюрингу. Более того, степени Тьюринга частично упорядочены , так что если степень Тьюринга множества X меньше степени Тьюринга множества Y , то любая (возможно, невычислимая) процедура, которая правильно решает, находятся ли числа в Y, может быть эффективно преобразована в процедуру, которая правильно решает, находятся ли числа в X. Именно в этом смысле степень Тьюринга множества соответствует его уровню алгоритмической неразрешимости.

Степени Тьюринга были введены Постом (1944), а многие фундаментальные результаты были получены Клини и Постом (1954). С тех пор степени Тьюринга стали областью интенсивных исследований. Многие доказательства в этой области используют технику доказательства, известную как метод приоритета .

В оставшейся части статьи слово « множество» будет относиться к множеству натуральных чисел. Множество X называется сводимым по Тьюрингу к множеству Y , если существует оракул Тьюринга , который принимает решение о членстве в X , когда дан оракул о членстве в Y. Обозначение X ≤ _T Y указывает, что X сводимо по Тьюрингу к Y.

Два множества X и Y определяются как эквивалентные по Тьюрингу, если X сводимо по Тьюрингу к Y , а Y сводимо по Тьюрингу к X. Обозначение X ≡ _T Y указывает, что X и Y эквивалентны по Тьюрингу. Отношение ≡ _T можно рассматривать как отношение эквивалентности , что означает, что для всех множеств X , Y и Z :

• Х ≡ _Т Х
• X ≡ _T Y подразумевает Y ≡ _T X
• Если X ≡ _T Y и Y ≡ _T Z , то X ≡ _T Z.

Степень Тьюринга — это класс эквивалентности отношения ≡ _T. Обозначение [ X ] обозначает класс эквивалентности, содержащий множество X. Вся совокупность степеней Тьюринга обозначается .${\displaystyle {\mathcal {D}}}$

Степени Тьюринга имеют частичный порядок ≤, определенный так, что [ X ] ≤ [ Y ] тогда и только тогда, когда X ≤ _T Y . Существует уникальная степень Тьюринга, содержащая все вычислимые множества, и эта степень меньше любой другой степени. Она обозначается 0 (нулем), поскольку является наименьшим элементом частично упорядоченного множества . (Обычно для степеней Тьюринга используют полужирное начертание, чтобы отличать их от множеств. Когда не возникает путаницы, например, с [ X ], полужирное начертание не обязательно.)${\displaystyle {\mathcal {D}}}$

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

Для любого множества X обозначение X ′ обозначает множество индексов машин-оракулов, которые останавливаются (при указании их индекса в качестве входных данных) при использовании X в качестве оракула. ​​Множество X ′ называется скачком Тьюринга X . Скачок Тьюринга степени [ X ] определяется как степень [ X ′]; это допустимое определение, поскольку X ′ ≡ _T Y ′ всякий раз, когда X ≡ T _Y . Ключевым примером является 0 ′, степень проблемы остановки .

• Каждая степень Тьюринга счетно бесконечна , то есть содержит ровно множеств.${\displaystyle \алеф _{0}}$
• Существуют различные степени Тьюринга.${\displaystyle 2^{\алеф _{0}}}$
• Для каждой степени a выполняется строгое неравенство a < a ′.
• Для каждой степени a множество степеней ниже a счетно . Множество степеней выше a имеет размер .${\displaystyle 2^{\алеф _{0}}}$

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

• Существуют минимальные степени . Степень a минимальна , если a не равно нулю и между 0 и a нет степени . Таким образом, отношение порядка на степенях не является плотным порядком .
• Степени Тьюринга не упорядочены линейно по ≤ _T. ^[1 ]
• На самом деле, для каждой ненулевой степени a существует степень b, несравнимая с a .
• Существует множество попарно несравнимых степеней Тьюринга.${\displaystyle 2^{\алеф _{0}}}$
• Существуют пары степеней без наибольшей нижней границы. Таким образом, это не решетка .${\displaystyle {\mathcal {D}}}$
• Каждое счетное частично упорядоченное множество может быть вложено в степени Тьюринга.
• Бесконечная строго возрастающая последовательность a ₁ , a ₂ , ... степеней Тьюринга не может иметь наименьшую верхнюю границу, но она всегда имеет точную пару c , d такую, что ∀ e ( e < c ∧ e < d ⇔ ∃ i e ≤ a _i ), и, таким образом, она имеет (неединственные) наименьшие верхние границы.
• Предполагая аксиому конструктивности , можно показать, что существует максимальная цепочка степеней типа порядка . ^[2]${\displaystyle \омега _{1}}$

• Для каждой степени 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 .
• Теорема Поста устанавливает тесное соответствие между арифметической иерархией и конечно-итерированными скачками Тьюринга пустого множества.

• Симпсон (1977b) показал, что теория первого порядка в языке ⟨ ≤, = ⟩ или ⟨ ≤, ′, = ⟩ является много-однозначной эквивалентностью теории истинной арифметики второго порядка . Это указывает на то, что структура является чрезвычайно сложной.${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {D}}}$
• Шор и Сламан (1999) показали, что оператор перехода можно определить в структуре первого порядка с помощью языка ⟨ ≤, = ⟩ .${\displaystyle {\mathcal {D}}}$

Степень называется рекурсивно перечислимой (re) или вычислимо перечислимой (ce), если она содержит рекурсивно перечислимое множество . Каждая степень re ниже 0′ , но не каждая степень ниже 0′ является re. Однако множество является много-одно сводимым к 0′ тогда и только тогда, когда оно является re. ^[3]${\displaystyle А}$${\displaystyle А}$

• Сакс (1964): Степени re плотные; между любыми двумя степенями re есть третья степень re.
• Лаклан (1966a) и Йейтс (1966): Существуют две степени re, не имеющие наибольшей нижней границы в степенях re.
• Лаклан (1966a) и Йейтс (1966): Существует пара ненулевых степеней ре, точная нижняя граница которой равна 0 .
• Лаклан (1966b): Не существует пары степеней re, наибольшая нижняя граница которых равна 0 , а наименьшая верхняя граница равна 0′ . Этот результат неформально называется теоремой о неалмазе .
• Томасон (1971): Любая конечная дистрибутивная решетка может быть вложена в re-степени. Фактически, счетная безатомная булева алгебра может быть вложена таким образом, чтобы сохранялись супремумы и инфимумы .
• Lachlan & Soare (1980): Не все конечные решетки могут быть вложены в re-степени (через вложение, которое сохраняет супремумы и инфимумы). Конкретный пример показан справа. LA Harrington и TA Slaman (см. Nies, Shore & Slaman (1998)): Теория первого порядка re-степеней в языке ⟨ 0 , ≤, = ⟩ эквивалентна теории истинной арифметики первого порядка .

Кроме того, существует предельная лемма Шенфилда: множество A удовлетворяет тогда и только тогда, когда существует «рекурсивное приближение» к его характеристической функции: функция g такая, что для достаточно большого s , . ^[4]${\displaystyle [A]\leq _{T}\emptyset '}$${\displaystyle g(s)=\chi _{A}(s)}$

Множество A называется n -r e., если существует семейство функций такое, что: ^[4]${\displaystyle (A_{s})_{s\in \mathbb {N} }}$

• A _s является рекурсивным приближением A : для некоторого t , для любого s ≥ t мы имеем A _s ( x ) = A ( x ), в частности, смешивая A с его характеристической функцией. (Устранение этого условия дает определение A как «слабо n -re» ).
• A _s является « n -пробным предикатом»: для всех x , A ₀ ( x )=0 и мощность ≤n.${\displaystyle \{s\mid A_{s}(x)\neq A_{s+1}(x)\}}$

Свойства n -ре степеней: ^[4]

• Класс множеств степени n -re является строгим подклассом класса множеств степени ( n +1)-re.
• Для всех n >1 существуют две ( n +1)-re степени a , b с , такие, что сегмент не содержит n -re степеней.${\displaystyle \mathbf {a} \leq _{T}\mathbf {b} }$${\displaystyle \{\mathbf {c} \mid \mathbf {a} \leq _ {T} \mathbf {c} \leq _{T} \ mathbf {b} \}}$
• ${\displaystyle А}$и являются ( n +1)-ре тогда и только тогда, когда оба множества являются слабо- n -ре${\displaystyle {\overline {A}}}$

Эмиль Пост изучал степени Тьюринга и задался вопросом, существует ли степень re строго между 0 и 0′ . Проблема построения такой степени (или доказательства того, что ее не существует) стала известна как проблема Поста . Эта проблема была решена независимо Фридбергом и Мучником в 1950-х годах, которые показали, что эти промежуточные степени re существуют ( теорема Фридберга–Мучника ). Каждое из их доказательств развивало один и тот же новый метод построения степеней re, который стал известен как метод приоритета . Метод приоритета в настоящее время является основным методом установления результатов о наборах re.

Идея метода приоритетов для построения набора сброса 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 является re и удовлетворяет всем требованиям. Аргументы приоритета могут использоваться для доказательства многих фактов о re-наборах; используемые требования и способ, которым они удовлетворяются, должны быть тщательно выбраны для получения требуемого результата.

Например, простой (и, следовательно, невычислимый re) low X (low означает X ′=0′) может быть построен за бесконечное количество этапов следующим образом. В начале этапа n пусть T _n будет выходной (двоичной) лентой, отождествленной с набором индексов ячеек, куда мы поместили 1 до сих пор (так что X =∪ _n T _n ; T ₀ =∅); и пусть P _n ( m ) будет приоритетом для того, чтобы не выводить 1 в позиции m ; P ₀ ( m )=∞. На этапе n , если возможно (иначе ничего не делать на этапе), выбрать наименьшее i < n такое, что ∀ m P _n ( m )≠ i и машина Тьюринга i остановится за < n шагов на некотором входе S ⊇ T _n с ∀ m ∈ S \ T _n P _n ( m )≥ i . Выберите любой такой (конечный) S , установите T _{n +1} = S , и для каждой ячейки m , посещённой машиной i на S , установите P _{n +1} ( m ) = min( i , P _n ( m )), и установите все приоритеты > i на ∞, а затем установите одну ячейку приоритета ∞ (подойдёт любая), не входящую в S , на приоритет i . По сути, мы останавливаем машину i , если можем сделать это, не нарушая приоритетов < i , а затем устанавливаем приоритеты так, чтобы машины > i не нарушали остановку; все приоритеты в конечном счёте постоянны.

Чтобы увидеть, что X является низким, машина i останавливается на X тогда и только тогда, когда она останавливается за < n шагов на некотором T _{n ,} таком что машины < i , которые останавливаются на X, делают это за < n - i шагов (по рекурсии это равномерно вычислимо из 0′). X невычислимо, поскольку в противном случае машина Тьюринга могла бы остановиться на Y тогда и только тогда, когда Y \ X непусто, что противоречит конструкции, поскольку X исключает некоторые ячейки приоритета i для произвольно большого i ; и X является простым, потому что для каждого i число ячеек приоритета i конечно.

• Мартин мера

• Купер, СБ (2004). Теория вычислимости . Бока-Ратон, Флорида: Chapman & Hall/CRC. стр. 424. ISBN 1-58488-237-9.
• Катланд, Найджел Дж. (1980). Вычислимость, введение в теорию рекурсивных функций . Кембридж-Нью-Йорк: Cambridge University Press. стр. 251. ISBN 0-521-22384-9.; ISBN 0-521-29465-7 

• Амбос-Шпис, Клаус; Фейер, Питер (20 марта 2006 г.). "Степени неразрешимости" (PDF) . Получено 20 августа 2023 г. . Неопубликовано
• Эпштейн, Р. Л.; Хаас, Р.; Крамер, Л. Р. (1981). Леман, М.; Шмерль, Дж.; Соаре, Р. (ред.). Иерархии множеств и степени ниже 0. Конспект лекций по математике. Том 859. Springer-Verlag.
• Лерман, М. (1983). Степени неразрешимости. Перспективы математической логики . Берлин: Springer-Verlag. ISBN 3-540-12155-2.
• Одифредди, Пьерджорджио (1989). Классическая теория рекурсии . Исследования по логике и основаниям математики. Том 125. Амстердам: Северная Голландия. ISBN 978-0-444-87295-1. МР  0982269.
• Одифредди, Пьерджорджио (1999). Классическая теория рекурсии. Том II . Исследования по логике и основаниям математики. Том 143. Амстердам: Северная Голландия. ISBN 978-0-444-50205-6. МР  1718169.
• Роджерс, Хартли (1967). Теория рекурсивных функций и эффективная вычислимость . Кембридж, Массачусетс : MIT Press . ISBN 9780262680523. OCLC  933975989 . Получено 6 мая 2020 г. .
• Сакс, GE (1966). Степени неразрешимости . Annals of Mathematics Studies. Princeton University Press. ISBN 978-0-6910-7941-7. JSTOR  j.ctt1b9x0r8.
• Симпсон, Стивен Г. (1977a). «Степени неразрешимости: обзор результатов». Annals of Mathematics Studies . Studies in Logic and the Foundations of Mathematics. 90. Elsevier : 631–652. doi :10.1016/S0049-237X(08)71117-0. ISBN 9780444863881.
• Шенфилд, Джозеф Р. (1971). Степени неразрешимости . North-Holland/Elsevier. ISBN 978-0-7204-2061-6.
• Shore, R. (1993). "Теории степеней T, tt и wtt re: неразрешимость и далее". In Univ. Nac. del Sur, Bahía Blanca (ред.). Труды IX Латиноамериканского симпозиума по математической логике, часть 1 (Bahía Blanca, 1992) . Notas Lógica Mat. Vol. 38. pp. 61–70.
• Soare, Robert Irving (1987). Рекурсивно перечислимые множества и степени: исследование вычислимых функций и вычислимо генерируемых множеств . Перспективы математической логики. Берлин: Springer-Verlag. ISBN 3-540-15299-7.
• Soare, Robert Irving (1978). «Рекурсивно перечислимые множества и степени». Bull. Amer. Math. Soc . 84 (6): 1149–1181. doi : 10.1090/S0002-9904-1978-14552-2 . MR  0508451. S2CID  29549997.

• Chong, CT; Yu, Liang (декабрь 2007 г.). «Максимальные цепи в степенях Тьюринга». Journal of Symbolic Logic . 72 (4): 1219–1227. doi :10.2178/jsl/1203350783. JSTOR  27588601. S2CID  38576214.
• ДеАнтонио, Джаспер (24 сентября 2010 г.). "Степени Тьюринга и отсутствие у них линейного порядка" (PDF) . Получено 20 августа 2023 г.
• Клини, Стивен Коул ; Пост, Эмиль Л. (1954), «Верхняя полурешетка степеней рекурсивной неразрешимости», Annals of Mathematics , вторая серия, 59 (3): 379–407, doi :10.2307/1969708, ISSN  0003-486X, JSTOR  1969708, MR  0061078
• Лаклан, Алистер Х. (1966a), «Нижние оценки для пар рекурсивно перечислимых степеней», Труды Лондонского математического общества , 3 (1): 537–569, CiteSeerX  10.1.1.106.7893 , doi :10.1112/plms/s3-16.1.537.
• Лаклан, Алистер Х. (1966b), «Невозможность нахождения относительных дополнений для рекурсивно перечислимых степеней», J. Symb. Log. , 31 (3): 434–454, doi :10.2307/2270459, JSTOR  2270459, S2CID  30992462.
• Лаклан, Алистер Х.; Соаре, Роберт Ирвинг (1980), «Не каждая конечная решетка вложима в рекурсивно перечислимые степени», Advances in Mathematics , 37 : 78–82, doi : 10.1016/0001-8708(80)90027-4
• Нис, Андре; Шор, Ричард А.; Сламан, Теодор А. (1998), «Интерпретируемость и определимость в рекурсивно перечислимых степенях», Труды Лондонского математического общества , 77 (2): 241–291, CiteSeerX  10.1.1.29.9588 , doi :10.1112/S002461159800046X, ISSN  0024-6115, MR  1635141, S2CID  16488410
• Пост, Эмиль Л. (1944), «Рекурсивно перечислимые множества положительных целых чисел и проблемы их решения», Бюллетень Американского математического общества , 50 (5): 284–316, doi : 10.1090/S0002-9904-1944-08111-1 , ISSN  0002-9904, MR  0010514
• Сакс, GE (1964), «Рекурсивно перечислимые степени плотны», Annals of Mathematics , вторая серия, 80 (2): 300–312, doi :10.2307/1970393, JSTOR  1970393
• Shore, Richard A .; Slaman, Theodore A. (1999), «Определение скачка Тьюринга», Mathematical Research Letters , 6 (6): 711–722, doi : 10.4310/mrl.1999.v6.n6.a10 , ISSN  1073-2780, MR  1739227
• Симпсон, Стивен Г. (1977b). «Теория первого порядка степеней рекурсивной неразрешимости». Annals of Mathematics . Вторая серия. 105 (1): 121–139. doi :10.2307/1971028. ISSN  0003-486X. JSTOR  1971028. MR  0432435.
• Thomason, SK (1971), "Подрешетки рекурсивно перечислимых степеней", Z. Math. Logik Grundlag. Math. , 17 : 273–280, doi :10.1002/malq.19710170131
• Йейтс, CEM (1966), «Минимальная пара рекурсивно перечислимых степеней», Журнал символической логики , 31 (2): 159–168, doi :10.2307/2269807, JSTOR  2269807, S2CID  38778059