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

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

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

Очевидно, что к вычислимым функциям следует отнести все константы, т.е. все натуральные числа 0,1,2... . Нет необходимости включать в базис бесконечное множество констант. Достаточно 0 и функции следования f(x)= x+1, (x').

Кроме того в базис включается семейство функций тождества (или введения фиктивных переменных)

(x₁,...x_n)=x_m (m<=n)

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

(h,g₁,...g_m)=h(g₁(x₁,...x_n)...g_m(x₁,...x_n)).

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

Оператором примитивной рекурсии называются подстановки, удовлетворяющие системе уравнений

f(x₁,...,x_n)= g(x₁,...,x_n)

f(x₁,...,x_n,y+1)= h(x₁,...,x_n,y,f(x₁,...,x_n,y)),

которая называется схемой примитивной рекурсии.

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

В формально-индуктивном виде это определение выглядит следующим образом:

1. Функции 0, Х', для всех натуральных m и n являются примитивно-рекурсивными.

2. Если h,g₁,...g_m – примитивно-рекурсивные функции, то – примитивно-рекурсивная функция.

3. Если g(x₁,...x_n),h(x₁,...x_m,y,z) – примитивно-рекурсивные функции, то – примитивно-рекурсивная функция.

4. Других примитивно-рекурсивных функций нет.

Примерами примитивно-рекурсивных функций являются

1. .

2. .

3. .

Отношение R(x₁,...x_n) называется примитивно-рекурсивным, если примитивно-рекурсивна его характеристическая функция

.

6.2.4 ПР-операторы

Оператор называется примитивно-рекурсивным (ПР), если он сохраняет примитивную рекурсивность функций, т.е. если результат его применения дает снова примитивно-рекурсивную функцию.

Операторы и являются ПР-операторами по определению.

Еще один ПР-оператор – оператор условного перехода , который по функциям и и предикату строит функцию

Существует теорема: если , и вычислимы по Тьюрингу, то разветвление и по также вычислимо.

В силу этой теоремы ПР-оператор вычислим по Тьюрингу.

Обобщение опреатора перехода на случай многозначного перехода по , из которых истиннен всегда только один , также примитивно-рекурсивно.

Ограниченный оператор минимизации m – применяется к предикатам.

Из предиката с помощью оператора получается функция .

Ограничение z в операторе дает гарантию окончания вычислений, поскольку оно оценивает сверху число вычислений предиката .

Если (ПР-оператор), то для вычисления f понадобится k+1 вычисление g и k вычислений h. В силу конечности общего числа операторов и , использованных для построения f из базисных функций, для любого k можно оценить количество элементарных действий для вычисления f.

Еще один ПР-оператор – оператор одновременной рекурсии – точнее целое семейство .

C его помощью строится рекурсивное описание сразу нескольких функций от (n-1)-ой переменной, причем значение каждой функции в точке y+1 зависит от значения всех функций в точке y.

По существу, совместная рекурсия дает рекурсивное описание функции-вектора.

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

1. Все примитивно-рекурсивные функции всюду опре-делены. Это следует из того, что простейшие функции всюду определены, а и это свойство сохраняют.

2. Строго говоря, мы имеем дело не с функциями, а с их примитивно-рекурсивным описанием. Различие здесь имеет тот же смысл, что и различие между функциями и их представлением в виде формул.

Возникает вопрос: все ли функции являются примитивно-рекурсивными? Простые теоретико-множественные соображения пока-зывают, что нет.

Функция называется частично-рекурсивной, если она может быть построена из простейших функций: 0, х`, с помощью конечного числа применений , и m-оператора.

По определению m-оператор применяется к предикатам. Поскольку в теории рекурсивных функций истинность предиката всегда связана со справедливостью некоторого равенства, то m-оператору можно придать стандартную форму:

Будучи применен к вычислимой функции m-оператор снова дает вычислимую функцию.

Однако эта процедура может не привести к результату: когда на данном наборе уравнение не имеет решения. В таком случае функция считается неопределенной.

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

Частично-рекурсивная функция называется общерекурсивной, если она всюду определена.