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

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

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

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

Если на все три вопроса есть положительный ответ, то истина, в противном случае — ложь.${\ Displaystyle Т_ {1} (е, я, х)}$

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

Существует соответствующая примитивно-рекурсивная функция , которая, если она истинна, возвращает результат функции с индексом на входе .${\ Displaystyle U}$${\ Displaystyle Т_ {1} (е, я, х)}$${\ Displaystyle U (х)}$${\ Displaystyle е}$${\ Displaystyle я}$

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