Введение
В информатике и математической логике степень Тьюринга (названная в честь Алана Тьюринга) или мера неразрешимости множества натуральных чисел определяет степень алгоритмической неразрешимости этого множества.
In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set.
Обзор
Понятие степени Тьюринга является фундаментальным в теории вычислимости, где множества натуральных чисел часто рассматриваются как задачи принятия решений. Степень Тьюринга множества – это мера сложности решения задачи принятия решений, связанной с этим множеством, то есть определения, принадлежит ли произвольное число данному множеству. Два множества Тьюрингово эквивалентны, если они имеют одинаковую степень неразрешимости; каждая степень Тьюринга представляет собой совокупность Тьюрингово эквивалентных множеств, так что два множества принадлежат разным степеням Тьюринга тогда и только тогда, когда они не являются Тьюрингово эквивалентными. Более того, степени Тьюринга частично упорядочены, и если степень Тьюринга множества X меньше степени Тьюринга множества Y, то любая (возможно, невычислимая) процедура, корректно решающая, принадлежит ли число Y, может быть эффективно преобразована в процедуру, корректно решающую, принадлежит ли число X. Именно в этом смысле степень Тьюринга множества соответствует его уровню алгоритмической неразрешимости. С тех пор степени Тьюринга являются областью интенсивных исследований. Многие доказательства в этой области используют технику доказательства, известную как приоритетный метод.
Основные свойства степеней Тьюринга
Каждая степень Тьюринга счетно бесконечна, то есть содержит ровно счётных множеств. Существует счётное количество различных степеней Тьюринга. Для каждой степени a строгое неравенство a < a′ выполняется. Для каждой степени a множество степеней ниже a счетно. Множество степеней выше a имеет мощность континуума.
Структура степеней Тьюринга
В структуре степеней Тьюринга проведено огромное количество исследований. Данный обзор перечисляет лишь некоторые из множества известных результатов. Общий вывод, который можно сделать из этих исследований, заключается в том, что структура степеней Тьюринга крайне сложна.
Свойства заказа
Есть минимальные степени. Степень a минимальна, если a ненулевая и не существует степени между 0 и a. Таким образом, отношение порядка на степенях не является отношением плотного порядка. Степени Тьюринга не линейно упорядочены отношением ≤T.
В действительности, для каждой ненулевой степени a существует степень b, несравнимая с a. Существует множество попарно несравнимых степеней Тьюринга. Существуют пары степеней, не имеющих наибольшей нижней границы. Следовательно, это не решётка. Любое счётное частично упорядоченное множество может быть вложено в степени Тьюринга. Бесконечная строго возрастающая последовательность a1, a2, … степеней Тьюринга не обязательно имеет наименьшую верхнюю границу, но она всегда имеет точную пару c, d такую, что ∀e (e<c ∧ e<d ⇔ ∃i e≤ai), и, таким образом, имеет (не единственные) минимальные верхние границы. Предполагая аксиому конструктивности, можно показать, что существует максимальная цепь степеней порядка типа ω1.
In fact, for every nonzero degree a there is a degree b incomparable with a. There is a set of pairwise incomparable Turing degrees. There are pairs of degrees with no greatest lower bound. Thus is not a lattice. Every countable partially ordered set can be embedded in the Turing degrees. An infinite strictly increasing sequence a1, a2, of Turing degrees cannot have the least upper bound, but it always has an exact pair c, d such that ∀e (e<c∧e<d ⇔ ∃i e≤ai), and thus it has (non unique) minimal upper bounds. Assuming the axiom of constructibility, it can be shown there is a maximal chain of degrees of order type .
Свойства, связанные со скачком
Для каждой степени a существует степень, строго лежащая между a и a′. Фактически, существует счетное семейство попарно несравнимых степеней между a и a′. Инверсия прыжка: степень a имеет вид b′, если и только если 0′ ≤ a. Для любой степени a существует степень b, такая что a < b и b′ = a′; такая степень b называется низкой относительно a. Существует бесконечная последовательность степеней a<sub>i</sub>, такая что a′<sub>i+1</sub> ≤ a<sub>i</sub> для каждого i. Теорема Поста устанавливает тесную связь между арифметической иерархией и конечно итерированными прыжками Тьюринга пустого множества.
Логические свойства
показал, что теория первого порядка в языке 1=〈 ≤, = 〉 или 1=〈 ≤, ′, = 〉 эквивалентна теории истинной арифметики второго порядка по редукции мощности один к одному. Это указывает на то, что структура крайне сложна. показал, что оператор скачка определим в структуре первого порядка с языком 1=〈 ≤, = 〉.
Рекурсивно перечисляемые степени Тьюринга
Степень называется рекурсивно перечислимой (r. e.) или вычислимо перечислимой (c. e.), если она содержит рекурсивно перечислимое множество. Каждая r.e. степень ниже 0′, но не каждая степень ниже 0′ является r.e. Однако множество является приводимым по одному ко множеству 0′ тогда и только тогда, когда оно является r.e.
: The r. e. degrees are dense; between any two r. e. degrees there is a third r. e. degree. and : There are two r. e. degrees with no greatest lower bound in the r. e. degrees. and : There is a pair of nonzero r. e. degrees whose greatest lower bound is 0.
: There is no pair of r. e. degrees whose greatest lower bound is 0 and whose least upper bound is 0′. This result is informally called the nondiamond theorem. : Every finite distributive lattice can be embedded into the r. e. degrees. In fact, the countable atomless Boolean algebra can be embedded in a manner that preserves suprema and infima. : Not all finite lattices can be embedded in the r. e. degrees (via an embedding that preserves suprema and infima). A particular example is shown to the right. L. A. Harrington and T. A. Slaman (see ): The first order theory of the r. e. degrees in the language 〈 0, ≤, = 〉 is many one equivalent to the theory of true first order arithmetic. Additionally, there is Shoenfield's limit lemma, a set A satisfies iff there is a "recursive approximation" to its characteristic function: a function g such that for sufficiently large s,
A set A is called n r e. if there is a family of functions such that:
As is a recursive approximation of A: for some t, for any s≥t we have As(x) = A(x), in particular conflating A with its characteristic function. (Removing this condition yields a definition of A being "weakly n r. e.")
As is an "n trial predicate": for all x, A0(x)=0 and the cardinality of is ≤n.
Properties of n r. e. degrees:
The class of sets of n r. e. degree is a strict subclass of the class of sets of (n+1) r. e. degree. For all n>1 there are two (n+1) r. e. degrees a, b with , such that the segment contains no n r. e. degrees. and are (n+1) r. e. iff both sets are weakly n r. e.
: r.e. степени плотны; между любыми двумя r.e. степенями существует третья r.e. степень. и : Существуют две r.e. степени, не имеющие наибольшей нижней границы в r.e. степенях. и : Существует пара ненулевых r.e. степеней, наибольшая нижняя граница которых равна 0. : Не существует пары r.e. степеней, наибольшая нижняя граница которых равна 0, а наименьшая верхняя граница равна 0′. Этот результат неформально называется теоремой о неалмазе. : Каждая конечная дистрибутивная решетка может быть вложена в r.e. степени. Фактически, счетная безатомная булева алгебра может быть вложена таким образом, чтобы сохранялись супремумы и инфимумы. : Не все конечные решетки могут быть вложены в r.e. степени (через вложение, сохраняющее супремумы и инфимумы). Конкретный пример показан справа. Л. А. Харрингтон и Т. А. Сламан (см. ): Теория первого порядка r.e. степеней в языке 〈 0, ≤, = 〉 эквивалентна по приводимости по одному теории истинной арифметики первого порядка. Кроме того, существует предельная лемма Шоенфилда: множество A удовлетворяет условию, если существует «рекурсивное приближение» к его характеристической функции: функция g, такая, что для достаточно больших s,
: The r. e. degrees are dense; between any two r. e. degrees there is a third r. e. degree. and : There are two r. e. degrees with no greatest lower bound in the r. e. degrees. and : There is a pair of nonzero r. e. degrees whose greatest lower bound is 0.
: There is no pair of r. e. degrees whose greatest lower bound is 0 and whose least upper bound is 0′. This result is informally called the nondiamond theorem. : Every finite distributive lattice can be embedded into the r. e. degrees. In fact, the countable atomless Boolean algebra can be embedded in a manner that preserves suprema and infima. : Not all finite lattices can be embedded in the r. e. degrees (via an embedding that preserves suprema and infima). A particular example is shown to the right. L. A. Harrington and T. A. Slaman (see ): The first order theory of the r. e. degrees in the language 〈 0, ≤, = 〉 is many one equivalent to the theory of true first order arithmetic. Additionally, there is Shoenfield's limit lemma, a set A satisfies iff there is a "recursive approximation" to its characteristic function: a function g such that for sufficiently large s,
A set A is called n r e. if there is a family of functions such that:
As is a recursive approximation of A: for some t, for any s≥t we have As(x) = A(x), in particular conflating A with its characteristic function. (Removing this condition yields a definition of A being "weakly n r. e.")
As is an "n trial predicate": for all x, A0(x)=0 and the cardinality of is ≤n.
Properties of n r. e. degrees:
The class of sets of n r. e. degree is a strict subclass of the class of sets of (n+1) r. e. degree. For all n>1 there are two (n+1) r. e. degrees a, b with , such that the segment contains no n r. e. degrees. and are (n+1) r. e. iff both sets are weakly n r. e.
Множество A называется n r.e., если существует семейство функций таких, что:
As является рекурсивным приближением к A: для некоторого t, для любого s ≥ t мы имеем As(x) = A(x), в частности, отождествляя A с его характеристической функцией. (Удаление этого условия дает определение A как «слабо n r.e.».)
As является «n-кратным предикатом»: для всех x, A0(x) = 0 и кардинальность ≤ n.
: The r. e. degrees are dense; between any two r. e. degrees there is a third r. e. degree. and : There are two r. e. degrees with no greatest lower bound in the r. e. degrees. and : There is a pair of nonzero r. e. degrees whose greatest lower bound is 0.
: There is no pair of r. e. degrees whose greatest lower bound is 0 and whose least upper bound is 0′. This result is informally called the nondiamond theorem. : Every finite distributive lattice can be embedded into the r. e. degrees. In fact, the countable atomless Boolean algebra can be embedded in a manner that preserves suprema and infima. : Not all finite lattices can be embedded in the r. e. degrees (via an embedding that preserves suprema and infima). A particular example is shown to the right. L. A. Harrington and T. A. Slaman (see ): The first order theory of the r. e. degrees in the language 〈 0, ≤, = 〉 is many one equivalent to the theory of true first order arithmetic. Additionally, there is Shoenfield's limit lemma, a set A satisfies iff there is a "recursive approximation" to its characteristic function: a function g such that for sufficiently large s,
A set A is called n r e. if there is a family of functions such that:
As is a recursive approximation of A: for some t, for any s≥t we have As(x) = A(x), in particular conflating A with its characteristic function. (Removing this condition yields a definition of A being "weakly n r. e.")
As is an "n trial predicate": for all x, A0(x)=0 and the cardinality of is ≤n.
Properties of n r. e. degrees:
The class of sets of n r. e. degree is a strict subclass of the class of sets of (n+1) r. e. degree. For all n>1 there are two (n+1) r. e. degrees a, b with , such that the segment contains no n r. e. degrees. and are (n+1) r. e. iff both sets are weakly n r. e.
Свойства n r.e. степеней:
Класс множеств n r.e. степени является строгим подклассом класса множеств (n+1) r.e. степени. Для всех n > 1 существуют две (n+1) r.e. степени a, b с , такие, что отрезок не содержит n r.e. степеней. и являются (n+1) r.e. тогда и только тогда, когда оба множества слабо n r.e.
: The r. e. degrees are dense; between any two r. e. degrees there is a third r. e. degree. and : There are two r. e. degrees with no greatest lower bound in the r. e. degrees. and : There is a pair of nonzero r. e. degrees whose greatest lower bound is 0.
: There is no pair of r. e. degrees whose greatest lower bound is 0 and whose least upper bound is 0′. This result is informally called the nondiamond theorem. : Every finite distributive lattice can be embedded into the r. e. degrees. In fact, the countable atomless Boolean algebra can be embedded in a manner that preserves suprema and infima. : Not all finite lattices can be embedded in the r. e. degrees (via an embedding that preserves suprema and infima). A particular example is shown to the right. L. A. Harrington and T. A. Slaman (see ): The first order theory of the r. e. degrees in the language 〈 0, ≤, = 〉 is many one equivalent to the theory of true first order arithmetic. Additionally, there is Shoenfield's limit lemma, a set A satisfies iff there is a "recursive approximation" to its characteristic function: a function g such that for sufficiently large s,
A set A is called n r e. if there is a family of functions such that:
As is a recursive approximation of A: for some t, for any s≥t we have As(x) = A(x), in particular conflating A with its characteristic function. (Removing this condition yields a definition of A being "weakly n r. e.")
As is an "n trial predicate": for all x, A0(x)=0 and the cardinality of is ≤n.
Properties of n r. e. degrees:
The class of sets of n r. e. degree is a strict subclass of the class of sets of (n+1) r. e. degree. For all n>1 there are two (n+1) r. e. degrees a, b with , such that the segment contains no n r. e. degrees. and are (n+1) r. e. iff both sets are weakly n r. e.
Проблема Поста и приоритетный метод
Эмиль Пост изучал степени Тьюринга р. е. и спросил, существует ли степень р. е. строго между 0 и 0′. Проблема построения такой степени (или доказательства её несуществования) стала известна как проблема Поста. Эта проблема была решена независимо Фридбергом и Мучником в 1950-х годах, которые показали, что эти промежуточные r. e. степени действительно существуют (теорема Фридберга — Мучника). Каждый из них разработал новый метод построения r. e. степеней, который стал известен как метод приоритетов. Метод приоритетов в настоящее время является основным методом для установления результатов о р. е. множествах. Идея метода приоритетов при построении r. e. множества X состоит в перечислении счётной последовательности требований, которым X должен удовлетворять. Например, для построения множества X между 0 и 0′ достаточно удовлетворить требованиям Ae и Be для каждого натурального числа e, где Ae требует, чтобы машина-оракул с индексом e не вычисляла 0′ по X, а Be требует, чтобы машина Тьюринга с индексом e (без оракула) не вычисляла X. Эти требования помещаются в приоритетный порядок, который является биекцией требований и натуральных чисел. Доказательство проводится индуктивно, с одним этапом для каждого натурального числа; эти этапы можно рассматривать как шаги времени, в течение которых множество X перечисляется. На каждом этапе числа могут быть добавлены в X или навсегда (если они не повреждены) исключены из X в попытке удовлетворить требованиям (то есть заставить их выполняться после перечисления всех элементов X). Иногда число может быть добавлено в X для удовлетворения одного требования, но это приведёт к тому, что ранее удовлетворённое требование станет неудовлетворённым (то есть будет повреждено). Приоритетный порядок требований используется для определения того, какое требование удовлетворять в этом случае. Неформальная идея заключается в том, что если требование повреждено, то оно в конечном итоге перестанет быть повреждено после того, как все требования с более высоким приоритетом перестанут быть повреждены, хотя не каждый аргумент, основанный на приоритетах, обладает этим свойством. Необходимо доказать, что результирующее множество X является r. e. и удовлетворяет всем требованиям. Аргументы, основанные на приоритетах, могут быть использованы для доказательства многих фактов о р. е. множествах; используемые требования и способ их удовлетворения должны быть тщательно выбраны для получения требуемого результата. Например, простой (и, следовательно, невычислимый р. е.) низкий X (низкий означает X′=0′) может быть построен в бесконечном количестве этапов следующим образом. В начале этапа n пусть Tn будет выходной (бинарной) лентой, отождествляемой с множеством индексов ячеек, в которые мы поместили 1 на данный момент (так X=∪n Tn; T0=∅); и пусть Pn(m) будет приоритетом для невывода 1 в позицию m; P0(m)=∞. На этапе n, если это возможно (в противном случае ничего не делать на этом этапе), выберите наименьшее i<n такое, что ∀m Pn(m)≠i и машина Тьюринга i останавливается менее чем за n шагов на некотором входе S⊇Tn с ∀m∈S\Tn Pn(m)≥i. Выберите любое такое (конечное) S, установите Tn+1=S, и для каждой ячейки m, посещённой машиной i на S, установите Pn+1(m) = min(i, Pn(m)), и установите все приоритеты >i в ∞, а затем установите одну ячейку с приоритетом ∞ (любую) не в S в приоритет i. По сути, мы заставляем машину i остановиться, если можем сделать это, не нарушая приоритетов <i, а затем устанавливаем приоритеты, чтобы предотвратить нарушение остановки машинами >i; все приоритеты в конечном итоге становятся постоянными. Чтобы увидеть, что X является низким, машина i останавливается на X тогда и только тогда, когда она останавливается менее чем за n шагов на некотором Tn, таком, что машины <i, которые останавливаются на X, делают это менее чем за n шагов (по рекурсии, это равномерно вычислимо по 0′). X невычислимо, поскольку в противном случае машина Тьюринга могла бы остановиться на Y тогда и только тогда, когда Y\X не пусто, что противоречит построению, поскольку X исключает некоторые ячейки с приоритетом i для произвольно больших i; и X является простым, потому что для каждого i число ячеек с приоритетом i конечно.