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

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

Определение

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

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

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

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

{ Displaystyle T_ {k} (е, i_ {1}, ldots, i_ {k}, x)}

,

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

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

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

{ Displaystyle е (п) simeq U ( му х , Т (е, п, х))}

,

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

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

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

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

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

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

{ Displaystyle К = {е { mbox {}}: { mbox {}} существует 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}, Икс)}}

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

Эта конструкция может быть расширена выше в арифметической иерархии, как в Теорема Поста (сравните Hinman 2005, с. 397). Например, если набор ${ Displaystyle А substeq mathbb {N} ^ {к + 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 Пи _ {п + 1} ^ {0}}$ полный.

Примечания

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