В математической логике и информатике , в общей рекурсивной функции , частично рекурсивной функции , или ц-рекурсивной функции является частичной функцией от натуральных чисел до натуральных чисел , что является «вычислимым» в интуитивном смысле. Если функция является полной, она также называется общей рекурсивной функцией (иногда сокращается до рекурсивной функции ). [1] В теории вычислимости показано, что μ-рекурсивные функции - это в точности функции, которые могут быть вычислены машинами Тьюринга [2] [4](это одна из теорем, подтверждающих тезис Черча – Тьюринга ). Μ-рекурсивные функции тесно связаны с примитивно рекурсивными функциями , и их индуктивное определение (ниже) основано на определении примитивных рекурсивных функций. Однако не каждая полностью рекурсивная функция является примитивной рекурсивной функцией - наиболее известным примером является функция Аккермана .
Другие эквивалентные классы функций - это функции лямбда-исчисления и функции, которые могут быть вычислены с помощью алгоритмов Маркова .
Подмножество всех общих рекурсивных функций со значениями в {0,1} известно в теории сложности вычислений как класс сложности R .
Определение
В М-рекурсивная функция (или общие рекурсивные функции ) представляют собой частичные функции , которые принимают конечные кортежи натуральных чисел и возвращают единственное натуральное число. Это наименьший класс частичных функций, который включает начальные функции и замкнут относительно композиции, примитивной рекурсии и оператора μ .
Наименьший класс функций, включающий исходные функции и замкнутый относительно композиции и примитивной рекурсии (т.е. без минимизации), - это класс примитивно рекурсивных функций . Хотя все примитивно рекурсивные функции являются тотальными, это не относится к частичным рекурсивным функциям; например, минимизация функции-преемника не определена. Примитивные рекурсивные функции являются подмножеством общих рекурсивных функций, которые являются подмножеством частичных рекурсивных функций. Например, можно доказать , что функция Аккермана полностью рекурсивна и не является примитивной.
Примитивные или «базовые» функции:
- Постоянные функции C n k : для каждого натурального числа и каждый
Альтернативные определения вместо этого используют нулевую функцию как примитивную функцию, которая всегда возвращает ноль, и построили постоянные функции из нулевой функции, функции-преемника и оператора композиции. - Функция преемника S:
- Функция проекции (также называемая функцией идентичности ): для всех натуральных чисел. такой, что :
Операторы ( область определения функции, определяемой оператором, представляет собой набор значений аргументов, так что каждое приложение функции, которое должно выполняться во время вычисления, обеспечивает четко определенный результат):
- Оператор композиции (также называемый оператором подстановки ): для m-арной функции и m k-арных функций :
Это значит, что определяется, только если а также все определены. - Оператор примитивной рекурсии : Учитывая k -арную функциюи k +2 -арная функция:
Это значит, что определяется, только если а также определены для всех - Оператор минимизации : Для ( k +1) -арной функции, k -арная функция определяется:
Интуитивно минимизация ищет - начиная поиск с 0 и продвигаясь вверх - наименьший аргумент, который заставляет функцию возвращать ноль; если такого аргумента нет или если встречается аргумент, для которого f не определено, то поиск никогда не прекращается, и не определено для аргумента
( Примечание : в некоторых учебниках используется μ-оператор, как определено здесь, [5] [6] другие, такие как [7] [8], требуют, чтобы μ-оператор применялся к полным функциямТолько. Хотя это ограничивает μ-оператор по сравнению с данным здесь определением, класс μ-рекурсивных функций остается тем же, что следует из теоремы Клини о нормальной форме (см. Ниже ). [5] [6] Единственное отличие состоит в том, что становится неразрешимым вопрос о том, определяет ли конкретное определение функции μ-рекурсивную функцию, поскольку невозможно решить, является ли вычислимая (т.е. μ-рекурсивная) функция тотальной. [7] )
Сильное равенство операторможет использоваться для сравнения частичных μ-рекурсивных функций. Это определено для всех частичных функций f и g так, что
выполняется тогда и только тогда, когда для любого выбора аргументов либо определены обе функции и их значения равны, либо обе функции не определены.
Полная рекурсивная функция
Общая рекурсивная функция называется тотальной рекурсивной функцией, если она определена для каждого входа или, что то же самое, если она может быть вычислена полной машиной Тьюринга . Невозможно вычислимо сказать, является ли данная общая рекурсивная функция полной - см. Проблема с остановкой .
Эквивалентность другим моделям вычислимости
В эквивалентности моделей вычислимости проводится параллель между машинами Тьюринга, которые не завершаются для определенных входных данных, и неопределенным результатом для этого входа в соответствующей частично рекурсивной функции. Оператор неограниченного поиска не определяется правилами примитивной рекурсии, поскольку они не обеспечивают механизма для «бесконечных циклов» (неопределенных значений).
Теорема о нормальной форме
Нормальная форма теоремы из - Клини говорит , что для каждого к существуют примитивно рекурсивные функции а также такое, что для любой μ-рекурсивной функции с k свободными переменными существует e такое, что
- .
Число e называется индексом или числом Гёделя для функции f . [9] : 52–53 Следствием этого результата является то, что любая μ-рекурсивная функция может быть определена с использованием одного экземпляра оператора μ, примененного к (общей) примитивно-рекурсивной функции.
Мински (1967) отмечает (как и Булос-Берджесс-Джеффри (2002) стр. 94–95), что U, определенный выше, по сути является μ-рекурсивным эквивалентом универсальной машины Тьюринга :
- Чтобы построить U, нужно записать определение общерекурсивной функции U (n, x), которая правильно интерпретирует число n и вычисляет соответствующую функцию от x. Построение U напрямую потребовало бы, по существу, того же количества усилий и, по сути, тех же идей , которые мы вложили в построение универсальной машины Тьюринга. (курсив в оригинале, Минский (1967) с. 189)
Символизм
В литературе используется ряд различных символизмов. Преимуществом использования символики является вывод функции путем «вложения» операторов один в другой, что легче записать в компактной форме. Далее мы будем сокращать строку параметров x 1 , ..., x n как x :
- Постоянная функция : Клини использует "C"п
д( x ) = q "и Boolos-Burgess-Jeffrey (2002) (BBJ) используют сокращение" const n ( x ) = n ":
- например, C 7
13 (r, s, t, u, v, w, x) = 13 - например, const 13 (r, s, t, u, v, w, x) = 13
- например, C 7
- Функция-преемник : Клини использует x 'и S для «преемника». Поскольку «преемник» считается примитивным, в большинстве текстов апостроф используется следующим образом:
- S (a) = a +1 = def a ', где 1 = def 0', 2 = def 0 '' и т. Д.
- Функция идентичности : Клини (1952) использует "Uн
я"для обозначения функции идентичности по переменным x i ; BBJ использует идентификатор функции идентичностин
япо переменным от x 1 до x n :
- U н
я( x ) = идентификатор н
я( х ) = х я - например, U 7
3 = id 7
3 (r, s, t, u, v, w, x) = t
- Оператор композиции (подстановки) : Клини использует полужирный шрифт Sm
n(не путать с его S для «преемника» ! ). Верхний индекс «m» относится к m- й функции «f m », тогда как нижний индекс «n» относится к n- й переменной «x n »:
- Если нам дано h ( x ) = g (f 1 ( x ), ..., f m ( x ))
- h ( x ) = Sп
м(g, f 1 , ..., f m )
- h ( x ) = Sп
- Аналогичным образом, но без нижних и верхних индексов, BBJ пишет:
- h ( x ' ) = Cn [g, f 1 , ..., f m ] ( x )
- Примитивная рекурсия : Клини использует символ « R n (базовый шаг, шаг индукции)», где 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 = U1
1а) - шаг индукции: f (b ', a) = (f (b, a))' = g (b, f (b, a), a) = g (b, c, a) = c '= S (U3
2(б, в, а))
- R 2 {U 1
1(а), S [(U 3
2(б, в, а)]} - Пр {У 1
1(а), S [(U 3
2(б, в, а)]}
- базовый шаг: f (0, a) = a = U1
Пример : Клини дает пример того, как выполнить рекурсивный вывод f (b, a) = b + a (обратите внимание на перестановку переменных a и b). Он начинается с 3-х начальных функций
- S (а) = а '
- U1
1(а) = а - U3
2(b, c, a) = c - g (b, c, a) = S (U3
2(b, c, a)) = c ' - базовый шаг: h (0, a) = U1
1а)
- шаг индукции: h (b ', a) = g (b, h (b, a), a)
Он прибывает в:
- а + Ь = R 2 [U 1
1, S3
1(S, U 3
2)]
- а + Ь = R 2 [U 1
Примеры
Смотрите также
Рекомендации
- ^ https://plato.stanford.edu/entries/recursive-functions/#PartRecuFuncPartRecuFuncREC
- ^ Стэнфордская энциклопедия философии , Entry Recursive Functions , Sect.1.7: «[Класс μ-рекурсивных функций] оказывается совпадающим с классом вычислимых по Тьюрингу функций, введенным Аланом Тьюрингом, а также с классом λ -определяемые функции, введенные Алонзо Черчем ".
- Перейти ↑ Kleene, Stephen C. (1936). «λ-определимость и рекурсивность» . Математический журнал герцога . 2 (2): 340–352. DOI : 10,1215 / s0012-7094-36-00227-2 .
- ^ Тьюринг, Алан Мэтисон (декабрь 1937 г.). «Вычислимость и λ-определимость». Журнал символической логики . 2 (4): 153–163. JSTOR 2268280 . Схема доказательства на стр.153: [3]
- ^ a b Enderton, HB, Математическое введение в логику, Academic Press, 1972
- ^ a b Булос, GS, Берджесс, JP, Джеффри, Р.С., Вычислимость и логика, Cambridge University Press, 2007
- ^ a b Джонс, Н. Д., Вычислимость и сложность: с точки зрения программирования, MIT Press, Кембридж, Массачусетс, Лондон, Англия, 1997 г.
- ^ Kfoury, AJ, Р. Моль, М. А. Арбиб, программирование подход к вычислимости, 2е изд., Springer-Verlag, Berlin, Heidelberg, НьюЙорк, 1982
- ^ Стивен Коул Клини (январь 1943 г.). «Рекурсивные предикаты и кванторы» (PDF) . Труды Американского математического общества . 53 (1): 41–73. DOI : 10.1090 / S0002-9947-1943-0007371-8 .
- Клини, Стивен (1991) [1952]. Введение в метаматематику . Walters-Noordhoff и Северная Голландия. ISBN 0-7204-2103-9.
- Соаре, Р. (1999) [1987]. Рекурсивно перечислимые множества и степени: исследование вычислимых функций и вычислимых порожденных множеств . Springer-Verlag. ISBN 9783540152996.
- Минский, Марвин Л. (1972) [1967]. Вычисления: конечные и бесконечные машины . Прентис-Холл. С. 210–5. ISBN 9780131654495.
- На страницах 210-215 Мински показывает, как создать μ-оператор, используя модель регистровой машины , тем самым демонстрируя ее эквивалентность общерекурсивным функциям.
- Булос, Джордж ; Берджесс, Джон ; Джеффри, Ричард (2002). «6.2 Минимизация» . Вычислимость и логика (4-е изд.). Издательство Кембриджского университета. С. 70–71. ISBN 9780521007580.
Внешние ссылки
- Стэнфордская энциклопедия философии
- Компилятор для преобразования рекурсивной функции в эквивалентную машину Тьюринга.