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

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

Обзор

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

Два множества эквивалентны по Тьюрингу , если они имеют одинаковый уровень неразрешимости; каждая степень Тьюринга представляет собой набор эквивалентных по Тьюрингу множеств, так что два множества находятся в разных степенях Тьюринга именно тогда, когда они не эквивалентны по Тьюрингу. Более того, степени Тьюринга частично упорядочены , так что если степень Тьюринга набора 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 ≡ _TZ , то X ≡ _TZ .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эмиль Пост изучил 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 конечно.

Смотрите также

Мартин мера

Примечания

^ ДеАнтонио 2010, с. 9.
^ Чонг и Ю 2007, с. 1224.
^ Одифредди 1989, с. 252, 258.
^ abc Эпштейн, Хаас и Крамер 1981.