Одно из нескольких эквивалентных определений вычислимой функции
В математической логике и информатика, общая рекурсивная функция (часто сокращается до рекурсивная функция ) или μ-рекурсивная функция, является частичной функцией от натуральных чисел до натуральных чисел, что является "вычислимым" в интуитивном смысле. В теории вычислимости показано, что μ-рекурсивные функции - это в точности функции, которые могут быть вычислены машинами Тьюринга (это одна из теорем, поддерживающих Черч. –Тезис Тьюринга ). Μ-рекурсивные функции тесно связаны с примитивно-рекурсивными функциями, и их индуктивное определение (ниже) основано на определении примитивно-рекурсивных функций. Однако не каждая μ-рекурсивная функция является примитивной рекурсивной функцией - наиболее известным примером является функция Аккермана.
. Другими эквивалентными классами функций являются функции лямбда-исчисления и функции, которые могут вычисляться с помощью алгоритмов Маркова.
Подмножество всех полных рекурсивных функций со значениями в {0,1} известно в теории вычислительной сложности как класс сложности R.
Содержание
- 1 Определение
- 2 Эквивалентность с другими моделями вычислимости
- 3 Теорема о нормальной форме
- 4 Символизм
- 5 Примеры
- 6 См. Также
- 7 Ссылки
- 8 Внешние ссылки
Определение
μ-рекурсивные функции (или общерекурсивные функции ) - это частичные функции, которые принимают конечные наборы натуральных чисел и возвращают одно натуральное число. Они представляют собой наименьший класс частичных функций, который включает в себя начальные функции и закрывается по композиции, примитивной рекурсии и оператору μ.
Наименьший класс функций, включая исходные функции и закрытый по композиции и примитивной рекурсии (т. Е. без минимизации) - это класс примитивных рекурсивных функций. Хотя все примитивные рекурсивные функции являются тотальными, это не относится к частичным рекурсивным функциям; например, минимизация функции-преемника не определена. Примитивные рекурсивные функции являются подмножеством общих рекурсивных функций, которые являются подмножеством частичных рекурсивных функций. Например, можно доказать, что функция Аккермана полностью рекурсивна и не является примитивной.
Примитивные или «базовые» функции:
- Постоянные функции C n: для каждого натурального числа и каждого . . Альтернативные определения используют вместо этого нулевую функцию как примитивную функцию, которая всегда возвращает ноль, и построили постоянные функции из нулевой функции, преемницы функция и оператор композиции.
- Функция-последователь S: .
- Функция проекции (также называемая функцией идентичности ): для всех натуральных чисел. такой, что :.
Операторы (область функции, определяемая оператором, представляет собой набор значений аргументов, так что каждое приложение функции, которое должно выполняться во время вычисления, обеспечивает четко определенный результат):
- Состав оператор (также называемый оператором подстановки ): дана m-арная функция и m k-арных функций :. . Это означает, что определяется, только если и все определены.
- Оператор примитивной рекурсии : Учитывая k- арная функция и k + 2 -арная функция :. . Это означает, что определяется, только если и определены для всех
- оператор минимизации : дана (k + 1) -арная функция , k-арная функция определяется следующим образом:. . Интуитивно, минимизация ищет— начало поиска с 0 и продвижение вверх - наименьший аргумент, который заставляет функцию возвращать ноль; если такого аргумента нет или если встречается аргумент, для которого f не определено, поиск никогда не прекращается, и не определено для аргумента . (Примечание: в некоторых учебниках используется μ-оператор, как определено здесь, в других, например, требуется, чтобы μ-оператор применялся к общим функциям Только . Хотя это ограничивает μ-оператор по сравнению с приведенным здесь определением, класс μ-рекурсивных функций остается прежним, что следует из теоремы Клини о нормальной форме. Единственное отличие состоит в том, что становится неразрешимым, удовлетворяет ли некоторый текст требованиям, предъявляемым к базовым функциям и операторам, поскольку не является полуразрешимым (следовательно, неразрешимым), является ли вычислимая (т. Е. Μ-рекурсивная) функция полной.)
Оператор строгого равенства может использоваться для сравнения частичных μ-рекурсивных функций. Это определено для всех частичных функций f и g, так что
выполняется тогда и только тогда, когда для любого выбора аргументов либо определены обе функции и их значения равны, либо обе функции не определены.
Эквивалентность с другими моделями вычислимости
В эквивалентности моделей вычислимости проводится параллель между машинами Тьюринга, которые не заканчиваются на определенные входы и неопределенный результат для этого входа в соответствующей частично рекурсивной функции. Оператор неограниченного поиска не определяется правилами примитивной рекурсии, поскольку они не обеспечивают механизма для «бесконечных циклов» (неопределенных значений).
Теорема о нормальной форме
A Теорема о нормальной форме, принадлежащая Клини, говорит, что для каждого k существуют примитивные рекурсивные функции и такая, что для любой μ-рекурсивной функции с k свободных переменных существует такая e, что
- .
Число e называется индекс или число Гёделя для функции f. Следствием этого результата является то, что любая μ-рекурсивная функция может быть определена с использованием единственного экземпляра оператора μ, примененного к (общей) примитивной рекурсивной функции.
Мински (1967) замечает (как и Булос-Берджесс-Джеффри (2002) стр. 94–95), что U, определенный выше, по существу является μ-рекурсивным эквивалентом универсальной машины Тьюринга :
- Построить U - значит записать определение общерекурсивной функции U (n, x), которая правильно интерпретирует число n и вычисляет соответствующую функцию от x. прямое построение U потребовало бы, по сути, того же количества усилий и, по сути, тех же идей, которые мы вложили в построение универсальной машины Тьюринга. (курсив в оригинале, Минский (1967) с. 189)
Символизм
В литературе используется ряд различных символизмов. Преимуществом использования символики является вывод функции путем «вложения» операторов один в другой, что проще записать в компактной форме. Далее мы будем сокращать строку параметров x 1,..., x n как x:
- Постоянная функция : Клини использует "C. q(x) = q "и Boolos-Burgess-Jeffrey (2002) (BBJ) используют сокращение" const n( x) = n ":
- например. C. 13(r, s, t, u, v, w, x) = 13
- например, const 13 (r, s, t, u, v, w, x) = 13
- Функция-последователь : Клини использует x 'и S для «наследника». Поскольку «преемник» считается примитивным, в большинстве текстов апостроф используется следующим образом:
- S (a) = a +1 = def a ', где 1 = def 0 ', 2 = def 0' 'и т. Д.
- Функция идентичности : Клини (1952) использует "U. i" для обозначения функции идентичности по переменным x я ; B-B-J используют идентификатор функции идентификации. iнад переменными x 1 до x n:
- U. i( x) = id. i( x) = x i
- , например. U. 3= id. 3(r, s, t, u, v, w, x) = t
- Оператор композиции (подстановки) : Клини использует полужирный шрифт S. n(не для следует путать с его S для "преемника" ! ). Верхний индекс «m» относится к m функции «f m », тогда как нижний индекс «n» относится к переменной n «x n":
- . Если нам задано h (x ) = g (f 1(x),..., f m(x))
- h(x) = S. m(g, f 1,..., f m)
- В аналогичным образом, но без нижних и верхних индексов, BBJ записывает:
- h (x ') = Cn [g, f 1,..., f m](x)
- Primitive Recursion : Клини использует символ «R (базовый шаг, индукционный шаг)», где n указывает количество переменных, BBJ использует «Pr (базовый шаг, индукционный шаг) (x ) ". Дано:
- базовый шаг: h (0, x ) = f (x ) и
- шаг индукции: h (y + 1, x ) = g (y, h (y, x),x)
- ) Пример: определение примитивной рекурсии a + b:
- базовый шаг: f (0, a) = a = U. 1(a)
- шаг индукции: f (b ', a) = (f (b, a))' = g (b, f (b, a), a) = g (b, c, a) = c '= S (U. 2(b, c, a))
- R {U. 1(a), S [(U. 2(b, c, a)]}
- Pr {U. 1(a), S [(U. 2(b, c, a)]}
Пример : Клини приводит пример того, как выполнить рекурсивный вывод f (b, a) = b + a (обратите внимание на изменение переменных a и b). Он начинает с 3 исходных функций
- S (a) = a '
- U. 1(a) = a
- U. 2(b, c, a) = c
- g (b, c, a) = S (U. 2(b, c, a)) = c '
- базовый шаг: h (0, a) = U. 1(a)
- шаг индукции: h (b ', a) = g (b, h (b, a), a)
Он достигает:
- a + b = R [U. 1, S. 1(S, U. 2)]
Примеры
См. Также
Ссылки
Внешние ссылки