Степень PA - PA degree

В математической области теория вычислимости, а Степень PA это Степень Тьюринга который вычисляет полное расширение Арифметика Пеано (Jockusch 1987). Эти степени тесно связаны с функциями без неподвижных точек (DNR) и были тщательно исследованы в теории рекурсии.

Фон

В теории рекурсии ${displaystyle phi _{e}}$ обозначает вычислимая функция с индексом (программа) е в некоторой стандартной нумерации вычислимых функций, и ${displaystyle phi _{e}^{B}}$ обозначает евычислимая функция с использованием набора B натуральных чисел как оракул.

Множество А натуральных чисел Приводимый по Тьюрингу к набору B если есть вычислимая функция что, учитывая оракул для множества B, вычисляет характеристическая функция χ_А из набора А. То есть есть е такой, что ${displaystyle chi _{A}=phi _{e}^{B}}$. Это отношение обозначается А ≤_Т B; отношение ≤_Т это Предварительный заказ.

Два набора натуральных чисел Эквивалент Тьюринга если каждый из них сводится по Тьюрингу к другому. Обозначение А ≡_Т B указывает А и B эквивалентны Тьюрингу. Отношение ≡_Т является отношением эквивалентности, известным как эквивалентность Тьюринга. А Степень Тьюринга представляет собой набор наборов натуральных чисел, такие что любые два набора в коллекции эквивалентны по Тьюрингу. Эквивалентно, степень Тьюринга - это класс эквивалентности отношения ≡_Т.

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

Функция ж из натуральных чисел в натуральные числа называется диагонально нерекурсивный (DNR) если для всех п, ${displaystyle f(n)ot =phi _{n}(n)}$ (здесь неравенство выполняется по определению, если ${displaystyle phi _{n}(n)}$ не определено). Если диапазон ж есть множество {0,1}, то ж это DNR₂ функция. Известно, что есть функции DNR, которые не вычисляют никакого DNR.₂ функция.

Завершение арифметики Пеано

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

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

Поскольку PA является эффективной теорией первого порядка, завершения PA можно охарактеризовать как бесконечные пути через конкретное вычислимое поддерево 2^<ω. Таким образом, степени PA - это в точности степени, которые вычисляют бесконечный путь через это дерево.

Характеристики

Степени PA закрываются вверх в градусах Тьюринга: если а степень PA и а ≤_Т б тогда б степень PA.

Степень Тьюринга 0‘, То есть степень проблема остановки, является степенью PA. Существуют также степени PA не выше 0‘. Например, теорема о низком базисе подразумевает низкую степень ПА. С другой стороны, Антонин Кучера доказал, что существует степень меньше, чем 0«Который вычисляет функцию DNR, но не является степенью PA (Jockusch 1989: 197).

Карл Джокуш и Роберт Соаре (1972) доказали, что степени PA - это в точности степени DNR₂ функции.

По определению степень является PA тогда и только тогда, когда она вычисляет путь через дерево дополнений арифметики Пеано. Имеет место более сильное свойство: степень а является степенью PA тогда и только тогда, когда а вычисляет путь через каждый бесконечное вычислимое поддерево 2^<ω (Симпсон 1977).

Критерий полноты Арсланова

М. М. Арсланов дал характеристику которых к.э. полны (т.е. эквивалент Тьюринга ${displaystyle varnothing '}$). Для к.э. набор ${displaystyle Asubseteq mathbb {N} }$, ${displaystyle Aequiv _{mathrm {T} }varnothing '}$ если и только если ${displaystyle A}$ вычисляет функцию DNR. В частности, каждая степень PA - DNR.₂ и, следовательно, DNR, поэтому ${displaystyle varnothing '}$ единственный в. п. Степень PA.

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

• Базисная теорема (вычислимость)
• Лемма Кёнига

Рекомендации

• Карл Джокуш (1987), "Степени функций без неподвижных точек", Коллоквиум по логике '87, Фенстад, Фролов и Хильпинен, ред., Северная Голландия, ISBN  0-444-88022-4
• Карл Джокуш и Роберт Соар (1972), "⁰₁ классы и степени теории », Труды Американского математического общества, v. 173, pp. 33–56.
• Стивен Г. Симпсон (1977), «Степени неразрешимости: обзор результатов», Справочник по математической логике, Barwise (ed.), North-Holland, стр. 631–652. ISBN  0-444-86388-5