Jump to content

Общая рекурсивная функция

(Перенаправлено из Теории рекурсивных функций )

В математической логике и информатике общая рекурсивная функция , частично рекурсивная функция или μ-рекурсивная функция — это частичная функция преобразования натуральных чисел в натуральные числа, которая «вычислима» как в интуитивном смысле, так и в формальном . Если функция тотальная, ее также называют тотальной рекурсивной функцией (иногда сокращают до рекурсивной функции ). [1] В теории вычислимости показано, что µ-рекурсивные функции — это именно те функции, которые можно вычислить с помощью машин Тьюринга. [2] [4] (это одна из теорем, подтверждающих тезис Чёрча-Тьюринга ). Мю-рекурсивные функции тесно связаны с примитивно-рекурсивными функциями , и их индуктивное определение (ниже) основано на определении примитивно-рекурсивных функций. Однако не каждая тотально рекурсивная функция является примитивно-рекурсивной функцией — наиболее известным примером является функция Аккермана .

Другими эквивалентными классами функций являются функции лямбда-исчисления и функции, которые могут быть вычислены с помощью алгоритмов Маркова .

Подмножество всех тотально рекурсивных функций со значениями в {0,1} известно в теории сложности вычислений как класс сложности R .

Определение [ править ]

Мю -рекурсивные функции (или общерекурсивные функции ) — это частичные функции, которые принимают конечные кортежи натуральных чисел и возвращают одно натуральное число. Это наименьший класс частичных функций, который включает исходные функции и замкнут относительно композиции, примитивной рекурсии и оператора минимизации µ .

Наименьшим классом функций, включающим исходные функции и замкнутыми относительно композиции и примитивной рекурсии (т.е. без минимизации), является класс примитивно-рекурсивных функций . Хотя все примитивно-рекурсивные функции являются тотальными, этого нельзя сказать о частично-рекурсивных функциях; например, минимизация функции-преемника не определена. Примитивно-рекурсивные функции являются подмножеством тотально рекурсивных функций, которые являются подмножеством частично-рекурсивных функций. Например, можно доказать, что функция Аккермана является полностью рекурсивной и непримитивной.

Примитивные или «базовые» функции:

  1. Постоянные функции C к
    n
    : Для каждого натурального числа n и каждого k
    Альтернативные определения вместо этого используют нулевую функцию как примитивную функцию, которая всегда возвращает ноль, и строят константные функции из нулевой функции, функции-преемника и оператора композиции.
  2. Функция-преемник S:
  3. Функция проецирования (также называемая функцией идентичности ): для всех натуральных чисел такой, что :

Операторы ( область определения функции, определенной оператором, представляет собой набор значений аргументов, так что каждое применение функции, которое должно быть выполнено во время вычисления, дает четко определенный результат):

  1. Оператор композиции (также называемый оператором подстановки ): для данной m-арной функции и m k-арные функции :
    Это означает, что определяется только в том случае, если и все определены.
  2. Примитивный оператор рекурсии ρ : Учитывая k -арную функцию и k +2 -арная функция :
    Это означает, что определяется только в том случае, если и определены для всех
  3. Оператор минимизации µ : для заданной ( k +1)-арной функции , k -арная функция определяется:

Интуитивно понятно, что минимизация ищет — начиная поиск с 0 и продолжая вверх — наименьший аргумент, который заставляет функцию возвращать ноль; если такого аргумента нет или если встречается аргумент, для которого f не определен, то поиск никогда не завершается и не определено для аргумента

Хотя в некоторых учебниках используется оператор μ, как он определен здесь, [5] [6] другим нравится [7] [8] потребуем, чтобы µ-оператор применялся только к полным функциям f . Хотя это ограничивает µ-оператор по сравнению с определением, данным здесь, класс µ-рекурсивных функций остается тем же, что следует из теоремы Клини о нормальной форме (см. ниже ). [5] [6] Единственная разница состоит в том, что становится неразрешимым, определяет ли конкретное определение функции µ-рекурсивную функцию, так же как неразрешимо, является ли вычислимая (т. е. µ-рекурсивная) функция полной. [7]

Оператор равенства сильного может использоваться для сравнения частичных µ-рекурсивных функций. Это определено для всех частичных функций f и g, так что

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

Примеры [ править ]

Примеры, не связанные с оператором минимизации, можно найти в разделе Примитивно-рекурсивная функция#Examples .

Следующие примеры предназначены только для демонстрации использования оператора минимизации; их можно определить и без него, хотя и более сложным способом, поскольку все они примитивно рекурсивны.

  • Целочисленный квадратный корень из x можно определить как наименьшее значение z такое, что . Используя оператор минимизации, общее рекурсивное определение имеет вид , где Not , Gt и Mul логическое отрицание , «больше» и умножение, [9] соответственно. Фактически, равен 0 тогда и только тогда, когда держит. Следовательно является наименьшим z таким, что держит. отрицания Юнктор Not необходим, поскольку Gt кодирует истину с помощью 1 , а μ ищет 0 .

Следующие примеры определяют общерекурсивные функции, которые не являются примитивно-рекурсивными; следовательно, они не могут избежать использования оператора минимизации.

Полная рекурсивная функция [ править ]

Общерекурсивная функция называется тотально рекурсивной функцией, если она определена для каждого входного сигнала или, что то же самое, если она может быть вычислена с помощью тотальной машины Тьюринга . Невозможно вычислимо определить, является ли данная общерекурсивная функция полной - см. Проблема остановки .

Эквивалентность с другими моделями вычислимости [ править ]

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

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

Теорема о нормальной форме Клини гласит, что для каждого k существуют примитивно-рекурсивные функции. и такая, что для любой µ-рекурсивной функции с k свободными переменными существует e такое, что

.

Число e называется индексом или числом Гёделя для функции f . [10] : 52–53  Следствием этого результата является то, что любая µ-рекурсивная функция может быть определена с использованием одного экземпляра оператора µ, примененного к (полной) примитивно-рекурсивной функции.

Минский наблюдает за Определенное выше, по сути, является μ-рекурсивным эквивалентом универсальной машины Тьюринга :

Построить U — значит записать определение общерекурсивной функции U(n, x), которая правильно интерпретирует число n и вычисляет соответствующую функцию от x. непосредственное построение U потребовало бы, по существу, того же количества усилий и, по существу, тех же идей , которые мы вложили в построение универсальной машины Тьюринга. [11]

Символизм [ править ]

В литературе используется множество различных символов. Преимущество использования символизма заключается в том, что получение функции путем «вложения» операторов один в другой легче записать в компактной форме. Далее строка параметров x 1 , ..., x n сокращается как x :

  • Постоянная функция : Клини использует «C» н
    q
    ( x ) = q" и Булос-Берджесс-Джеффри (2002) (BBJ) используют аббревиатуру "const n ( x ) = n":
например С 7
13
( р, с, т, ты, v, ш, х) = 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 i ; BBJ использует идентификатор функции тождества н
    i
    над переменными от x 1 до x n :
В н
я
( Икс ) = идентификатор н
я
( Икс ) знак равно Икс я
например, У 7
3
= идентификатор 7
3
( р, с, т, ты, v, ш, Икс) = т
  • Оператор композиции (замены) : Клини использует жирный шрифт S. м
    n
    (не путать с его S, обозначающим «преемник» ! ). Верхний индекс «м» относится к м. й функции «f m », тогда как индекс «n» относится к n й переменная "x n ":
Если нам дано h( x ) = g( f 1 ( x ), ... , f m ( x ) )
час ( Икс ) = S н
м
(г, ж 1 , ... , ж м )
Аналогичным образом, но без подстрочных и надстрочных индексов, BBJ пишет:
h( x' )= Cn[g, f 1 ,..., f m ]( x )
  • Примитивная рекурсия : Клини использует символ « 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
    1
    (а)
  • шаг индукции: f(b',a) = (f(b,a))' = g(b, f(b,a),a) = g(b,c,a) = c' = S(U 3
    2
    ( б, в, а ))
Р 2 {U 1
1
(а), S [ (U 3
2
( б, в, а ) ] }
Пр{ У 1
1
(а), S[ (U 3
2
( б, в, а ) ] }

Пример : Клини приводит пример того, как выполнить рекурсивный вывод f(b, a) = b + a (обратите внимание на обращение переменных a и b). Он начинает с 3 начальных функций

  1. S(а) = а'
  2. В 1
    1
    (а) = а
  3. В 3
    2
    ( б, с, а ) = с
  4. g(b, c, a) = S(U 3
    2
    ( б, с, а )) = с'
  5. базовый шаг: h( 0, a ) = U 1
    1
    (а)
шаг индукции: h( b', a ) = g( b, h( b, a ), a )

Он приезжает:

а+б = Р 2 1
1
, С 3
1
(С, У 3
2
) ]

Примеры [ править ]

См. также [ править ]

Ссылки [ править ]

  1. ^ «Рекурсивные функции» . Стэнфордская энциклопедия философии . Лаборатория метафизических исследований Стэнфордского университета. 2021.
  2. ^ Стэнфордская энциклопедия философии входа , Рекурсивные функции , раздел 1.7: «[Класс µ-рекурсивных функций] совпадает с классом функций, вычислимых по Тьюрингу, введенными Аланом Тьюрингом, а также с классом λ -определяемые функции, введенные Алонсо Чёрчем » .
  3. ^ Клини, Стивен К. (1936). «λ-определимость и рекурсивность» . Математический журнал Дьюка . 2 (2): 340–352. дои : 10.1215/s0012-7094-36-00227-2 .
  4. ^ Тьюринг, Алан Мэтисон (декабрь 1937 г.). «Вычислимость и λ-определимость». Журнал символической логики . 2 (4): 153–163. дои : 10.2307/2268280 . JSTOR   2268280 . S2CID   2317046 . Схема доказательства на стр.153: [3]
  5. Перейти обратно: Перейти обратно: а б Эндертон, HB, Математическое введение в логику, Academic Press, 1972 г.
  6. Перейти обратно: Перейти обратно: а б Булос, Г.С., Берджесс, Дж.П., Джеффри, Р.К., Вычислимость и логика, Cambridge University Press, 2007 г.
  7. Перейти обратно: Перейти обратно: а б Джонс, Н.Д., Вычислимость и сложность: с точки зрения программирования, MIT Press, Кембридж, Массачусетс, Лондон, Англия, 1997 г.
  8. ^ Кфури, А.Дж., Р.Н. Молл и М.А. Арбиб, Программный подход к вычислимости, 2-е изд., Springer-Verlag, Берлин, Гейдельберг, Нью-Йорк, 1982 г.
  9. ^ определено в Примитивная рекурсивная функция#Соединители , Примитивная рекурсивная функция#Предикат равенства и Примитивная рекурсивная функция#Умножение
  10. ^ Стивен Коул Клини (январь 1943 г.). «Рекурсивные предикаты и кванторы» (PDF) . Труды Американского математического общества . 53 (1): 41–73. дои : 10.1090/S0002-9947-1943-0007371-8 .
  11. ^ Минский 1972 , стр. 189.
На страницах 210-215 Мински показывает, как создать μ-оператор, используя модель регистровой машины , тем самым демонстрируя его эквивалентность общерекурсивным функциям.

Внешние ссылки [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: f7b0f4f2cc20e732e0492e77c9d74083__1687607940
URL1:https://arc.ask3.ru/arc/aa/f7/83/f7b0f4f2cc20e732e0492e77c9d74083.html
Заголовок, (Title) документа по адресу, URL1:
General recursive function - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)