7. Происхождение рекурсивных функций.

Рекурсивные функции

(от  позднелатинского recursio — возвращение)

        название, закрепившееся за одним из наиболее распространённых вариантов уточнения общего понятия арифметического алгоритма, т.е. такого Алгоритма, допустимые исходные данные которого представляют собой системы натуральных чисел, а возможные результаты применения являются натуральными числами. Рекурсивные функции были введены в 30-х гг. 20 в. С. К. Клини, в свою очередь основывавшимся на исследованиях К. Гёделя, Ж. Эрбрана и др. математиков.

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

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

8. Основные понятия теории рекурсивных функций и тезис Чёрча.

Тезис Черча: класс алгоритмически (или машинно) вычислимых частичных числовых функций совпадает с классом всех частично рекурсивных функций. Иными словами, арифметическая функция, вычислимая в общем смысле, есть суть рекурсивная функция. Соотв.

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

9. Примитивно-рекурсивные функции.

примитивно рекурсивные функции — рекурсивные функции, получающиеся из исходных функций в результате конечного числа применений одних лишь операторов суперпозиции и примитивной рекурсии. Они образуют собственную часть класса общерекурсивных функций. В силу известной теоремы Клини о нормальной форме рекурсивной функции могут быть указаны такие конкретные примитивно рекурсивные функции U от одной переменной и Tn от n + 2 переменных, что для любой рекурсивной функции φ отn переменных и для любых натуральных чисел x1, . . ., xn имеет место равенство φ(x1, ..., xn) ≅ U(y), гдеу есть наименьшее из чисел z таких, что Tn(φ, x1, ..., xn,z) = 0 (здесь φ представляет собой т. н. геделев номер функции φ — число, которое эффективно строится по системе равенств, задающей функцию φ). Из этой теоремы, в частности, вытекает, что для рекурсивной функции от п переменных может быть построена универсальная рекурсивная функция от n+1 переменных, т. е. такая рекурсивная функцияФn, что для любой рекурсивной функции φ от n переменных и для любых натуральных чисел x1, . . .,xn имеет место условное равенство

         φ( x1, . . ., xn) ≅ Фn(x1, . . ., xn).

1. Примеры.

Укажем  на ряд широко известных арифметических функций, являющихся примитивно рекурсивными.

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

10. Вычислимость по Тьюрингу примитивно-рекурсивных функций.

11. Функции Аккермана.

Функция Аккермана — простой пример всюду определённой вычислимой функции, которая не является примитивно рекурсивной. Она принимает два неотрицательных целых числа в качестве параметров и возвращает натуральное число, обозначается  . Эта функция растёт очень быстро, например, число   настолько велико, что количество цифр в порядке этого числа многократно превосходит количество атомов в наблюдаемой части Вселенной.

12. Оператор минимизации.

Оператор минимизации Пусть имеется функция f(x₁,….x_n), принадлежащая множеству частичных арифметических функций (ЧАФ). Пусть существует какой то механизм ее вычисления, причем значение функции не определено тогда и только тогда, когда этот механизм работает бесконечно, не выдавая никакого определенного результата. Фиксируем какие-нибудь значения x₁,......,x_n-1 для первых n-1 аргументов функции f и рассмотрим уравнение: f(x₁,.....,x_n-1,y)=x_n  Чтобы найти решение y (натуральное) этого уравнения, будем вычислять при помощи указанного выше "механизма" последовательно значения f(x₁,...,x_n-1,y) для y=0,1,2,... Наименьшее значение a, для которого получится f(x₁,...x_n-1,a)=x_n, обозначим через μ_y(f(x₁,...,x_n-1,y)=x_n)  Описанный процесс нахождения выражения μ_y(f(x₁,...,x_n-1,y)=x_n) будет продолжаться бесконечно в следующих случаях:

• Значение f(x₁,.....,x_n-1,0) не определено;

• Значения f(x₁,.....,x_n-1,y) для y=0,1,...,a-1 определены, но отличны от x_n, а значение f(x₁,.....,x_n-1,a) – не определено;

• Значения f(x₁,.....,x_n-1,y) определены для всех y=0,1,2,... и отличны от x_n.

Во всех этих случаях значение выражения μ_y(f(x₁,...,x_n-1,y)=x_n) считается неопределенным. В остальных случаях описанный процесс обрывается и дает наименьшее решение y=a уравнения f(x₁,.....,x_n-1,y)=x_n.. Это решение, как сказано, и будет значением выраженияμ_y(f(x₁,...,x_n-1,y)=x_n). Например, для функции разности f(x,y)=x-y в соответствии с указанным смыслом символа μ, для всех x,y имеем: f(x,y)=x-y=μ_z(y+z=x)  Подсчет значений функции f(x,y)=x-y в этом случае будет проходить по двум сценариям.