степень ПА

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

Фон

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

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

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

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

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

Пополнения арифметики Пеано

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

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

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

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

Степени PA закрыты вверх в степенях Тьюринга: если a — степень PA и a ≤ _T b, то b — степень PA.

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

Карл Йокуш и Роберт Соаре (1972) доказали, что степени PA являются в точности степенями функций DNR ₂ .

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

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

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

См. также

Ссылки

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