Введение
Одно из нескольких эквивалентных определений вычислимой функции. В математической логике и информатике общая рекурсивная функция, частичная рекурсивная функция или μ-рекурсивная функция — это частичная функция от натуральных чисел к натуральным числам, которая "вычислима" в интуитивном и формальном смысле. Если функция тотальна, она также называется тотальной рекурсивной функцией (иногда сокращенно — рекурсивной функцией). В теории вычислимости показано, что μ-рекурсивные функции — это именно те функции, которые могут быть вычислены машинами Тьюринга (это одна из теорем, подтверждающих тезис Черча — Тьюринга). μ-рекурсивные функции тесно связаны с примитивно рекурсивными функциями, и их индуктивное определение (приведено ниже) строится на основе определения примитивно рекурсивных функций. Однако не каждая тотальная рекурсивная функция является примитивно рекурсивной функцией; наиболее известным примером является функция Аккермана. Другие эквивалентные классы функций — это функции лямбда-исчисления и функции, которые могут быть вычислены алгоритмами Маркова. Подмножество всех тотальных рекурсивных функций со значениями в в теории вычислительной сложности известно как класс сложности R.
In mathematical logic and computer science, a general recursive function, partial recursive function, or μ recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as in a formal one. If the function is total, it is also called a total recursive function (sometimes shortened to recursive function). In computability theory, it is shown that the μ recursive functions are precisely the functions that can be computed by Turing machines (this is one of the theorems that supports the Church–Turing thesis). The μ recursive functions are closely related to primitive recursive functions, and their inductive definition (below) builds upon that of the primitive recursive functions. However, not every total recursive function is a primitive recursive function—the most famous example is the Ackermann function. Other equivalent classes of functions are the functions of lambda calculus and the functions that can be computed by Markov algorithms. The subset of all total recursive functions with values in is known in computational complexity theory as the complexity class R.
Общая рекурсивная функция
Общая рекурсивная функция называется тотальной рекурсивной функцией, если она определена для любого набора входных данных, или, что эквивалентно, если она может быть вычислена полной машиной Тьюринга. Не существует вычислительного способа определить, является ли заданная общая рекурсивная функция тотальной – см. проблему останова.
Эквивалентность с другими моделями вычислимости
В эквивалентности моделей вычислимости проводится параллель между машинами Тьюринга, не завершающими работу для определенных входных данных, и неопределённым результатом для этих данных в соответствующей частично рекурсивной функции. Оператор неограниченного поиска не может быть определён правилами примитивной рекурсии, так как они не предоставляют механизма для "бесконечных циклов" (неопределённых значений).