Предикат T Клини

Концепция в теории вычислимости

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

Определение

Пример вызова T ₁ . Первый аргумент дает исходный код (на языке C , а не как число Гёделя e ) вычислимой функции, а именно функции Коллатца f . Второй аргумент дает натуральное число i, к которому должна быть применена f . Третий аргумент дает последовательность x шагов вычисления, имитирующую оценку f на i (как цепочку уравнений, а не как число последовательности Гёделя). Вызов предиката оценивается как true, поскольку x на самом деле является правильной последовательностью вычисления для вызова f (5), и заканчивается выражением, больше не включающим f . Функция U , примененная к последовательности x , вернет свое окончательное выражение, а именно 1.

Определение зависит от подходящей нумерации Гёделя , которая присваивает натуральные числа вычислимым функциям (заданным как машины Тьюринга ). Эта нумерация должна быть достаточно эффективной, чтобы, имея индекс вычислимой функции и входные данные для функции, можно было эффективно смоделировать вычисление функции на этих входных данных. Предикат получается путем формализации этой симуляции. ${\displaystyle T}$

Тернарное отношение принимает три натуральных числа в качестве аргументов. является истинным, если кодирует историю вычислений вычисляемой функции с индексом при запуске с входными данными , и программа останавливается на последнем шаге этой истории вычислений. То есть, ${\displaystyle T_{1}(e,i,x)}$ ${\displaystyle T_{1}(e,i,x)}$ ${\displaystyle x}$ ${\displaystyle e}$ ${\displaystyle i}$

• ${\displaystyle T_{1}}$сначала спрашивается, является ли число Гёделя конечной последовательности полных конфигураций машины Тьюринга с индексом , выполняющей вычисления на входе . ${\displaystyle x}$ ${\displaystyle \langle x_{j}\rangle }$ ${\displaystyle e}$ ${\displaystyle i}$
• Если да, то спрашивается, начинается ли эта последовательность с начального состояния вычисления и соответствует ли каждый последующий элемент последовательности одному шагу машины Тьюринга. ${\displaystyle T_{1}}$
• Если да, то наконец спрашивает, заканчивается ли последовательность остановкой машины. ${\displaystyle T_{1}}$ ${\displaystyle \langle x_{j}\rangle }$

Если на все три вопроса дан положительный ответ, то утверждение истинно, в противном случае — ложно. ${\displaystyle T_{1}(e,i,x)}$

Предикат является примитивно рекурсивным в том смысле, что существует примитивно рекурсивная функция, которая, учитывая входные данные для предиката, правильно определяет истинностное значение предиката на этих входных данных. ${\displaystyle T_{1}}$

Существует соответствующая примитивная рекурсивная функция, такая что если она истинна, то возвращает выход функции с индексом на входе . ${\displaystyle U}$ ${\displaystyle T_{1}(e,i,x)}$ ${\displaystyle U(x)}$ ${\displaystyle e}$ ${\displaystyle i}$

Поскольку формализм Клини прикрепляет несколько входов к каждой функции, предикат может использоваться только для функций, которые принимают один вход. Существуют дополнительные предикаты для функций с несколькими входами; отношение ${\displaystyle T_{1}}$

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

истинно, если кодирует останавливающееся вычисление функции с индексом на входах . ${\displaystyle x}$ ${\displaystyle e}$ ${\displaystyle i_{1},\ldots ,i_{k}}$

Как и , все функции примитивно рекурсивны. Из-за этого любая теория арифметики, способная представить каждую примитивно рекурсивную функцию, способна представить и . Примерами таких арифметических теорий являются арифметика Робинсона и более сильные теории, такие как арифметика Пеано . ${\displaystyle T_{1}}$ ${\displaystyle T_{k}}$ ${\displaystyle T}$ ${\displaystyle U}$

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

Предикаты могут быть использованы для получения теоремы Клини о нормальной форме для вычислимых функций (Soare 1987, стр. 15; Kleene 1943, стр. 52—53). Она утверждает, что существует фиксированная примитивная рекурсивная функция , такая, что функция вычислима тогда и только тогда, когда существует число , такое, что для всех выполняется ${\displaystyle T_{k}}$ ${\displaystyle U}$ ${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$ ${\displaystyle e}$ ${\displaystyle n_{1},\ldots ,n_{k}}$

${\displaystyle f(n_{1},\ldots ,n_{k})\simeq U(\mu x\,T_{k}(e,n_{1},\ldots ,n_{k},x))}$,

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

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

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

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

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

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

является -полным ( n +1)-арным предикатом. Таким образом, как только в теории арифметики получено представление предиката T _n , из него может быть получено представление -полного предиката. ${\displaystyle \Sigma _{1}^{0}}$ ${\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. Описанный здесь предикат был представлен в (Клини 1943) и (Клини 1952), и это то, что обычно называют «предикатом Клини T ». (Клини 1967) использует букву T для описания другого предиката, связанного с вычислимыми функциями, но который не может быть использован для получения теоремы Клини о нормальной форме.

Ссылки

• Питер Хинман, 2005, Основы математической логики , AK Peters. ISBN  978-1-56881-262-5
• Стивен Коул Клини (январь 1943 г.). «Рекурсивные предикаты и квантификаторы» (PDF) . Труды Американского математического общества . 53 (1): 41–73. doi : 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