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

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

Обзор

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

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

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

Тьюринговая эквивалентность

Основная статья: Редукция Тьюринга

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

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

• Икс ≡ _Т Икс
• X ≡ _T Y влечет Y ≡ _T X
• Если X ≡ _TY Y и то ≡ _T Z , X ≡ _T Z .

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

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

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

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

Основные свойства степеней Тьюринга

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

Структура степеней Тьюринга

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

Заказать недвижимость

• Есть минимальные степени . Степень a минимальна , если a нет степени не равна нулю и между 0 и a . Таким образом, отношение порядка на степенях не является плотным порядком .
• Степени Тьюринга не упорядочены линейно по ≤ _T .
• В самом деле, для каждой ненулевой степени a существует степень b, несравнимая с a .
• Есть набор $2^{\aleph _{0}}$ попарно несравнимые степени Тьюринга.
• Существуют пары степеней, у которых нет максимальной нижней границы. Таким образом ${\mathcal {D}}$ это не решетка .
• Любое счетное частично упорядоченное множество можно вложить в степени Тьюринга.
• Бесконечная строго возрастающая последовательность a ₁ , a ₂ , ... степеней Тьюринга не может иметь наименьшую верхнюю границу, но всегда имеет точную пару c , d такую, что ∀ e ( e < c ∧ e < d ⇔ ∃ i e ≤ a _i ), и, следовательно, он имеет (неединственные) минимальные верхние границы.
• Приняв аксиому конструктивности , можно показать, что существует максимальная цепочка степеней порядкового типа. $\omega _{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) показал, что теория первого порядка ${\mathcal {D}}$ в языке ⟨ ≤, = ⟩ или ⟨ ≤, ′, = ⟩ является много-единичным эквивалентом теории истинной арифметики второго порядка . Это указывает на то, что структура ${\mathcal {D}}$ является чрезвычайно сложным.
• Шор и Сламан (1999) показали, что оператор перехода определим в структуре первого порядка ${\mathcal {D}}$ с языком ⟨ ≤, = ⟩ .

Рекурсивно перечислимые степени Тьюринга

Конечная решетка, которую нельзя вложить в re степени.

Степень называется рекурсивно перечислимой (re) или вычислимо перечислимой (ce), если она содержит рекурсивно перечислимое множество . Каждая степень re ниже 0′ , но не каждая степень ниже 0′ является re. Однако набор $A$ сводится к 0 ' многим-одному, если и только если $A$ это повторно.

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

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

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

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

Свойства n -re градусов:

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

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

«Проблема почты» перенаправляется сюда. О другой «проблеме Поста» см. « Проблема с перепиской Поста » .

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

Например, простой (и, следовательно, невычислимый re) low X (низкий означает X ′=0′) может быть построен за бесконечное число этапов следующим образом. В начале этапа n пусть T _n будет выходной (двоичной) лентой, идентифицируемой с набором индексов ячеек, куда мы до сих пор поместили 1 (так что X =∪ _n T _n ; T ₀ =∅); и пусть Pn _{позиции} ( m ) будет приоритетом для отказа от вывода 1 в m ; п ₀ ( м )=∞. На этапе n , если это возможно (иначе на этом этапе ничего не делать), выберите наименьшее значение i < n такое, что ∀ m P _n ( m )≠ i и машина Тьюринга i останавливается за < n шагов на некотором входе S ⊇ T _n с ∀ м ∈ S \ Т _п п _п ( м )≥ я . Выберите любой такой (конечный) 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. ИСБН  1-58488-237-9 .
• Катленд, Найджел Дж. (1980). Вычислимость, введение в рекурсивную теорию функций . Кембридж-Нью-Йорк: Издательство Кембриджского университета. п. 251. ИСБН  0-521-22384-9 . ; ISBN   0-521-29465-7

Монографии и обзорные статьи (дипломный уровень)

• Амбос-Спис, Клаус; Фейер, Питер (20 марта 2006 г.). «Степени неразрешимости» (PDF) . Проверено 20 августа 2023 г. Неопубликовано
• Эпштейн, РЛ; Хаас, Р; Крамер, Л.Р. (1981). Леман, М; Шмерл, Дж.; Соаре, Р. (ред.). Иерархии множеств и степеней ниже 0 . Конспект лекций по математике. Том. 859. Шпрингер-Верлаг.
• Лерман, М. (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). Степени неразрешимости . Анналы математических исследований. Издательство Принстонского университета. ISBN  978-0-6910-7941-7 . JSTOR   j.ctt1b9x0r8 .
• Симпсон, Стивен Г. (1977a). «Степени неразрешимости: обзор результатов». Анналы математических исследований . Исследования по логике и основам математики. 90 . Эльзевир : 631–652. дои : 10.1016/S0049-237X(08)71117-0 . ISBN  9780444863881 .
• Шенфилд, Джозеф Р. (1971). Степени неразрешимости . Северная Голландия/Эльзевир. ISBN  978-0-7204-2061-6 .
• Шор, Р. (1993). «Теории T, tt и wtt re степеней: неразрешимость и за ее пределами». В унив. Нак. дель Сур, Баия-Бланка (ред.). Труды IX Латиноамериканского симпозиума по математической логике, Часть 1 (Баия Бланка, 1992) . Notas Logica Mat. Том. 38. С. 61–70.
• Соаре, Роберт Ирвинг (1987). Рекурсивно перечислимые множества и степени: исследование вычислимых функций и вычислимо порожденных множеств . Перспективы математической логики. Берлин: Springer-Verlag. ISBN  3-540-15299-7 .
• Соаре, Роберт Ирвинг (1978). «Рекурсивно перечислимые множества и степени» . Бык. амер. Математика. Соц . 84 (6): 1149–1181. дои : 10.1090/S0002-9904-1978-14552-2 . МР   0508451 . S2CID   29549997 .

Научные статьи

• Чонг, Коннектикут; Ю, Лян (декабрь 2007 г.). «Максимальные цепи в степенях Тьюринга» . Журнал символической логики . 72 (4): 1219–1227. дои : 10.2178/jsl/1203350783 . JSTOR   27588601 . S2CID   38576214 .
• ДеАнтонио, Джаспер (24 сентября 2010 г.). «Степени Тьюринга и отсутствие линейного порядка» (PDF) . Проверено 20 августа 2023 г.
• Клини, Стивен Коул ; Пост, Эмиль Л. (1954), «Верхняя полурешетка степеней рекурсивной неразрешимости», Annals of Mathematics , Second Series, 59 (3): 379–407, doi : 10.2307/1969708 , ISSN   0003-486X , JSTOR   1969708 , МР   0061078
• Лахлан, Алистер Х. (1966a), «Нижние границы для пар рекурсивно перечислимых степеней», Труды Лондонского математического общества , 3 (1): 537–569, CiteSeerX   10.1.1.106.7893 , doi : 10.1112/plms/s3 -16.1.537 .
• Лахлан, Алистер Х. (1966b), «Невозможность найти относительные дополнения для рекурсивно перечислимых степеней», J. Symb. Бревно. , 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 , МР   1635141 , С2КИД   16488410
• Пост, Эмиль Л. (1944), «Рекурсивно перечислимые множества положительных целых чисел и проблемы их решения», Бюллетень Американского математического общества , 50 (5): 284–316, doi : 10.1090/S0002-9904-1944-08111- 1 , ISSN   0002-9904 , МР   0010514
• Сакс, GE (1964), «Рекурсивно перечислимые степени плотны», Annals of Mathematics , Second Series, 80 (2): 300–312, doi : 10.2307/1970393 , JSTOR   1970393
• Шор, Ричард А .; Сламан, Теодор А. (1999), «Определение скачка Тьюринга», Mathematical Research Letters , 6 (6): 711–722, doi : 10.4310/mrl.1999.v6.n6.a10 , ISSN   1073-2780 , MR   1739227
• Симпсон, Стивен Г. (1977b). «Теория первого порядка степеней рекурсивной неразрешимости». Анналы математики . Вторая серия. 105 (1): 121–139. дои : 10.2307/1971028 . ISSN   0003-486X . JSTOR   1971028 . МР   0432435 .
• Томасон, С.К. (1971), "Подрешетки рекурсивно перечислимых степеней", Z. Math. Логик Грундлаг. Математика. , 17 : 273–280, doi : 10.1002/malq.19710170131
• Йейтс, CEM (1966), «Минимальная пара рекурсивно перечислимых степеней», Journal of Символическая логика , 31 (2): 159–168, doi : 10.2307/2269807 , JSTOR   2269807 , S2CID   38778059