Kleenes T предикат - Kleenes T predicate

В теория вычислимости, то Предикат T, впервые изученный математиком Стивен Коул Клини, это особый набор троек из натуральные числа что используется для представления вычислимые функции в формальные теории из арифметика. Неофициально Т предикат сообщает, компьютерная программа остановится при запуске с определенным входом, и соответствующий U функция используется для получения результатов вычислений, если программа действительно останавливается. Как и в случае с s_мин теорема, исходное обозначение, используемое Клини, стало стандартной терминологией для этого понятия.^[1]

Определение

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

В тернарное отношение Т₁(е,я,Икс) принимает в качестве аргументов три натуральных числа. Тройки чисел (е,я,Икс), принадлежащие отношению (те, для которых Т₁(е,я,Икс) истинно) определяются как именно те тройки, в которых Икс кодирует историю вычислений вычислимой функции с индексом е при запуске с вводом я, и программа останавливается на последнем этапе этой истории вычислений. То есть, Т₁ сначала спрашивает, есть ли Икс это Число Гёделя конечной последовательности ⟨Икс_j⟩ Полных конфигураций машины Тьюринга с индексом е, выполняя вычисление на входе я. Если так, Т₁ затем спрашивает, начинается ли эта последовательность с начального состояния вычисления и каждый последующий элемент последовательности соответствует одному шагу машины Тьюринга. Если это так, Т₁ наконец, спрашивает, может ли последовательность ⟨Икс_j⟩ Заканчивается остановкой машины. Если на все три вопроса есть положительный ответ, то Т₁(е,я,Икс) выполняется (верно). Иначе, Т₁(е,я,Икс) не выполняется (ложно).

Есть соответствующая функция U так что если Т(е,я,Икс) выполняется тогда U(Икс) возвращает результат функции с индексом е на входе я.

Поскольку формализм Клини связывает несколько входных данных с каждой функцией, предикат Т₁ может использоваться только для функций, которые принимают один вход. Есть дополнительные предикаты для функций с несколькими входами; Соотношение

${\displaystyle T_{k}(e,i_{1},\ldots ,i_{k},x)}$,

имеет место, если Икс кодирует остановку вычисления функции с индексом е на входах я₁,...,я_k.

Теорема о нормальной форме

В Т предикат может использоваться для получения Теорема Клини о нормальной форме для вычислимых функций (Soare 1987, p. 15; Kleene 1943, p. 52–53). Это заявляет, что существует примитивная рекурсивная функция U так что функция ж одного целочисленного аргумента вычислим тогда и только тогда, когда существует число е такой, что для всех п надо

${\displaystyle f(n)\simeq U(\mu x\,T(e,n,x))}$,

куда μ это μ оператор (${\displaystyle \mu x\,\phi (x)}$ наименьшее натуральное число, для которого ${\displaystyle \phi (x)}$ держит) и ${\displaystyle \simeq }$ выполняется, если обе стороны не определены или если обе определены и равны. Здесь U является универсальной операцией (не зависит от вычислимой функции ж), целью которого является извлечение из числа Икс (кодирование полной истории вычислений), возвращаемое оператором μ, просто значение ж(п), который был найден в конце расчета.

Формализация

В Т предикат примитивно рекурсивный в том смысле, что существует примитивная рекурсивная функция, которая, учитывая входные данные для предиката, правильно определяет значение истинности предиката на этих входных данных. Точно так же U функция примитивно рекурсивна.

Из-за этого любая теория арифметики, способная представить любую примитивно рекурсивную функцию, способна представить Т и U. Примеры таких арифметических теорий включают: Арифметика Робинсона и более сильные теории, такие как Арифметика Пеано.

Арифметическая иерархия

Помимо вычислимости кодирования, Т предикат может использоваться для генерации полных наборов в арифметическая иерархия. В частности, множество

${\displaystyle K=\{e{\mbox{ }}:{\mbox{ }}\exists xT(e,0,x)\}}$

что из того же Степень Тьюринга как проблема остановки, это ${\displaystyle \Sigma _{1}^{0}}$ полное унарное отношение (Soare 1987, с. 28, 41). В более общем плане набор

${\displaystyle K_{n+1}=\{\langle e,a_{1},\ldots ,a_{n}\rangle :\exists xT(e,a_{1},\ldots ,a_{n},x)\}}$

это ${\displaystyle \Sigma _{1}^{0}}$ полный (п+1) -арный предикат. Таким образом, однажды представление Т предикат получен в теории арифметики, представление ${\displaystyle \Sigma _{1}^{0}}$-полный предикат может быть получен из него.

Эта конструкция может быть расширена выше в арифметической иерархии, как в Теорема Поста (сравните Hinman 2005, с. 397). Например, если набор ${\displaystyle A\subseteq \mathbb {N} ^{k+1}}$ является ${\displaystyle \Sigma _{n}^{0}}$ завершить тогда набор

${\displaystyle \{\langle a_{1},\ldots ,a_{k}\rangle :\forall x(\langle a_{1},\ldots ,a_{k},x)\in A)\}}$

является ${\displaystyle \Pi _{n+1}^{0}}$ полный.

Примечания

1. Описанный здесь предикат был представлен в (Kleene 1943) и (Kleene 1952), и это то, что обычно называют "предикатом Клини". Т предикат ». (Kleene 1967) использует букву Т для описания другого предиката, связанного с вычислимыми функциями, но который нельзя использовать для получения теоремы Клини о нормальной форме.

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

• Питер Хинман, 2005 год, Основы математической логики, А. К. Петерс. ISBN  978-1-56881-262-5
• Стивен Коул Клини (январь 1943 г.). «Рекурсивные предикаты и кванторы» (PDF). Труды Американского математического общества. 53 (1): 41–73. Дои:10.1090 / S0002-9947-1943-0007371-8. Перепечатано в Неразрешимый, Мартин Дэвис, изд., 1965, стр. 255–287.
• —, 1952, Введение в метаматематику, Северная Голландия. Перепечатано Ishi Press, 2009 г., ISBN  0-923891-57-9.
• —, 1967. Математическая логика, Джон Вили. Перепечатано Dover, 2001, ISBN  0-486-42533-9.
• Роберт И. Соаре, 1987, Рекурсивно перечислимые множества и степени, Перспективы математической логики, Springer. ISBN  0-387-15299-7