Концепция степени Тьюринга является фундаментальной в теории вычислимости , где наборы натуральных чисел часто рассматриваются как проблемы принятия решений . Степень Тьюринга набора — это мера того, насколько сложно решить проблему принятия решения, связанную с набором, то есть определить, находится ли произвольное число в данном наборе.
Два множества эквивалентны по Тьюрингу , если они имеют одинаковый уровень неразрешимости; каждая степень Тьюринга представляет собой набор эквивалентных по Тьюрингу множеств, так что два множества находятся в разных степенях Тьюринга именно тогда, когда они не эквивалентны по Тьюрингу. Более того, степени Тьюринга частично упорядочены , так что если степень Тьюринга набора 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. Обозначается вся совокупность степеней Тьюринга .
Степени Тьюринга имеют частичный порядок ≤, определенный так, что [ X ] ≤ [ Y ] тогда и только тогда, когда X ≤ TY . Существует единственная степень Тьюринга, содержащая все вычислимые множества, и эта степень меньше любой другой степени. Он обозначается 0 (ноль), потому что это наименьший элемент ЧУУ . (Обычно для степеней Тьюринга используются жирные обозначения, чтобы отличить их от множеств. Когда путаницы не может возникнуть, например, с [ X ], жирный шрифт не нужен.)
Для любых множеств X и Y соединение X с Y, записанное X ⊕ Y , определяется как объединение множеств {2 n : n ∈ X } и {2 m +1 : m ∈ Y }. Степень Тьюринга X ⊕ Y — это наименьшая верхняя граница степеней X и Y . Таким образом, это соединение-полурешетка . Наименьшая верхняя граница степеней a и b обозначается a ∪ b . Известно, что не является решеткой , так как существуют пары степеней, у которых нет максимальной нижней границы.
Для любого набора X обозначение X ′ обозначает набор индексов машин-оракулов, которые останавливаются (если на входе указан их индекс) при использовании X в качестве оракула. Множество X ′ называется скачком Тьюринга X . Скачок Тьюринга степени [ X ] определяется как степень [ X ′]; это правильное определение, потому что X ′ ≡ TY ′ всякий раз, когда X ≡ TY . Ключевым примером является 0 ′, степень проблемы остановки .
Основные свойства степеней Тьюринга
Каждая степень Тьюринга счетно бесконечна , то есть содержит ровно множества.
Существуют различные степени Тьюринга.
Для каждой степени a выполняется строгое неравенство a < a ′.
Для каждой степени a множество степеней ниже a счетно . Набор степеней больше a имеет размер .
Структура степеней Тьюринга
Было проведено большое количество исследований структуры степеней Тьюринга. В следующем обзоре перечислены лишь некоторые из многих известных результатов. Один общий вывод, который можно сделать из исследования, заключается в том, что структура степеней Тьюринга чрезвычайно сложна.
Заказать недвижимость
Есть минимальные степени . Степень a минимальна , если a не равна нулю и между 0 и a нет степени . Таким образом, отношение порядка на степенях не является плотным порядком .
Степени Тьюринга не упорядочены линейно по ≤ T . [1]
В самом деле, для каждой ненулевой степени a существует степень b, несравнимая с a .
Существует набор попарно несравнимых степеней Тьюринга.
Существуют пары степеней, у которых нет максимальной нижней границы. Таким образом, это не решетка .
Любое счетное частично упорядоченное множество можно вложить в степени Тьюринга.
Бесконечная строго возрастающая последовательность степеней Тьюринга a 1 , a 2 , ... не может иметь наименьшую верхнюю границу, но всегда имеет точную пару c , d такую, что ∀ e ( e < c ∧ e < d ⇔ ∃ i e ≤ a i ), и, следовательно, он имеет (неединственные) минимальные верхние границы.
Приняв аксиому конструктивности , можно показать, что существует максимальная цепочка степеней порядкового типа . [2]
Свойства, связанные с прыжком
Для каждой степени 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 .
Шор и Сламан (1999) показали, что оператор перехода определим в структуре первого порядка с помощью языка ⟨ ≤, = ⟩ .
Рекурсивно перечислимые степени Тьюринга
Степень называется рекурсивно перечислимой (re) или вычислимо перечислимой (ce), если она содержит рекурсивно перечислимое множество . Каждая степень re ниже 0′ , но не каждая степень ниже 0′ является re. Однако множество можно свести к 0 ' многим одним, если и только если оно re. [3]
Сакс (1964): Степени re плотные; между любыми двумя re-степеньями есть третья re-степень.
Лахлан (1966а) и Йейтс (1966): Есть две степени re, у которых нет максимальной нижней границы.
Лахлан (1966а) и Йейтс (1966): Существует пара ненулевых градусов re, максимальная нижняя граница которых равна 0 .
Лахлан (1966b): Не существует пары re степеней, чья наибольшая нижняя граница равна 0 , а наименьшая верхняя граница равна 0′ . Этот результат неофициально называется неалмазной теоремой .
Лахлан и Соаре (1980): Не все конечные решетки могут быть вложены в степени re (посредством вложения, сохраняющего верхние и нижние точки). Конкретный пример показан справа. Л.А. Харрингтон и Т.А. Сламан (см. Nies, Shore & Slaman (1998)): Теория первого порядка re степеней в языке ⟨ 0 , ≤, = ⟩ эквивалентна теории истинной арифметики первого порядка. .
Кроме того, существует предельная лемма Шенфилда: набор A удовлетворяет тогда и только тогда, когда существует «рекурсивная аппроксимация» его характеристической функции: функция g такая, что для достаточно больших s , . [4]
Множество A называется n -r e. если существует семейство функций такое, что: [4]
As является рекурсивной аппроксимацией A : для некоторого t для любого s ≥ t мы имеем As ( x ) = A ( x ), в частности, объединяя A с его характеристической функцией. (Удаление этого условия дает определение A как «слабо n -re» )
As s является « n -пробным предикатом»: для всех x A 0 ( x )= 0 и мощность равна ≤n.
Свойства n -re степеней: [4]
Класс множеств n -й степени является строгим подклассом класса множеств ( n +1)-й степени.
Для всех n >1 существуют две ( n +1)-re степени a , b с , такие, что отрезок не содержит n -re степеней.
и являются ( 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 0 =∅); и пусть Pn ( m ) будет приоритетом для отказа от вывода 1 в позиции m ; п 0 ( м )=∞. На этапе 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 конечно.
Амбос-Спис, Клаус; Фейер, Питер (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.
Сакс, GE (1966). Степени неразрешимости . Анналы математических исследований. Издательство Принстонского университета. ISBN 978-0-6910-7941-7. JSTOR j.ctt1b9x0r8.
Симпсон, Стивен Г. (1977a). «Степени неразрешимости: обзор результатов». Анналы математических исследований . Исследования по логике и основам математики. Эльзевир . 90 : 631–652. дои : 10.1016/S0049-237X(08)71117-0. ISBN 9780444863881.
Шор, Р. (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 . MR 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, номер документа : 10.2307/2270459, JSTOR 2270459, S2CID 30992462.
Лахлан, Алистер Х.; Соаре, Роберт Ирвинг (1980), «Не каждая конечная решетка вкладывается в рекурсивно перечислимые степени», Advance 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, S2CID 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