Рекурсивные функции. Для ученых, которых интересуют лишь факты существования или не­существования

Для ученых, которых интересуют лишь факты существования или не­существования алгоритмов, а не сами алгоритмы, вовсе не обязательно изучать именно алгоритмы. Достаточно найти такие объекты, которые су­ществуют или не существуют в точности тогда же, когда и алгоритмы. Считают, что такими объектами являются рекурсивные функции. Пока­жем, как могут функции быть связанными с алгоритмами.

Как известно, величину w называют функцией, а величины x₁,x₂,…,x_n —

Аргументами, или независимыми переменными, если известен закон, ко­торый для различных наборов конкретных значений величин x1,x2,…,xn задает определенные значения величины w. При этом для каждого набора допускается одно-единственное значение функции. В частном случае функция может иметь одно независимое переменное (аргумент). Что за за­кон применяется для определения функции? Математика не накладывает никаких ограничений на него. Она допускает любой мыслимый закон. Но таким законом может быть некоторый алгоритм. В этом случае функцию называют вычислимой, так как имеется способ получения ее значений. Рекурсивными функциями называют один частный класс вычислимых функций. Алгоритмы, являющиеся законами их задания, мы будем назы­вать алгоритмами, сопутствующими рекурсивным функциям.

По Черчу числовая функция называется рекурсивной, если она отно­сится к одному из двух классов:

1. Базовым рекурсивным функциям (алгоритм получения таких функций считается очевидным)

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

Замечание. В первой редакции данного определения оператор минимизации отсутствует.

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

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

Базовые функции Базовые функции бывают трех типов:

1. Функции любого числа независимых переменных, тождественно равные нулю. Для краткости будем называть их «тождественный ноль» Их будем обозначать φ_n, где п — число аргументов. Например, к числу таких функций относятся у= φ₁(x), w=φ₃(x, у, z), w=φ_n(x₁,x₂,…,x_n). Сопутствующий алгоритм для этих функций гласит: «Если функ­циональный знак имеет вид φ_n, то любой совокупности значений аргу­ментов данной функции ставится в соответствие ее значение 0».

Напри­мер, f(x)=x-x, может быть обозначение: φ(x)=x-x≡0.

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

2. Функции любого числа независимых переменных, тождественно равные одному из аргументов. Обозначим их ψ_{n,i где} п — число аргументов, i — номер одного из аргументов 1< i < n). Сопутствующий этим функциям алгоритм гласит: «Если функциональный знак имеет вид ψ_n,i, то значением функций считать значение i -го (считая в функциональной записи слева направо) независимого переменного».

Например: ψ_1,3(x,y,z)=x.

Для тождественных функций ни n, ни i не может быть равно нулю.

3. Функции следования (иначе — получения последователя) одного независимого переменного. Обозначим их с помощью функционального знака λ(х). Сопутствующий этим функциям алгоритм гласит: «Если функциональный знак имеет вид λ(х), то значением функции считать число, непосредственно следующее за числом, являющимся значением аргумента». Операция «получения последователя», по-видимому, проще сложения. Дети сначала учатся считать, а потом уже овладевают сложе­нием. Первобытные люди тоже сначала овладели счетом, и лишь много позже возникла идея сложения чисел. Это вполне естественно, так как в ту пору числа изображали как последовательности черточек (зарубок). Последователь получали, добавляя еще одну зарубку.

Например: λ(х)=x+1; λ(3)=3+1=4.

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

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

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

В теории рекурсивных функции особое значение имеют три следую­щих оператора: Оператор суперпозиции, оператор примитивной рекурсии и оператор минимизации.

Оператор суперпозиции или подстановки. Слова суперпозиция и подстановка в данном случае имеют одно и то же значение. Этот оператор по функции F от п аргументов и по функциям f₁,f₂,…,f_n строит новую функцию Ф такую, что для нее справедливо тождест­во Ф≡ F(f₁,f₂,…,f_n).

Алгоритм, сопутствующий этому оператору, гласит: «Значения функций f₁,f₂,…,f_n принять за значения аргументов функции F и вычислить ее зна­чение». Оператор подстановки (суперпозиции) обозначим буквой С. Построение функции Ф из функций F и f_i с помощью оператора суперпозиции будем записывать так: Ф= С(F,f₁,f₂,…,f_n).

Алгоритм построения суперпозиции (для двух функций).

1. Выбираются две функции f, g.

2. Определяется аргумент x_k первой функции f, для которой будем осуществлять подстановку.

3. Подставляем значение аргумента в g и вычисляем её значение g_o.

4. x_k=g_o.

5. f_o=f(x₁,x₂,…,x_n)

Например, если в качестве F принять λ(х), а в качестве f₁ взять функцию λ(у), то с помощью операции суперпозиции получим функцию τ(у) = λ(λ(у)). Правило суперпозиции Суперпозиция двух рекурсивных функций является рекурсивной функ­цией.

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

Многократной суперпозицией является совокупность нескольких од­новременных суперпозиций, когда один аргумент первой функции меня­ется второй функцией, другой - третьей и так далее.

Пример: F(x,y)=x+y и даны две функции g(x), f(x). Построим суперпозицию: Ф =C(F,g(x),f(y))=g(x)+f(y).

Оператор примитивной рекурсии. Этот оператор по двум функциям, одна из которых имеет п- 1неза­висимых переменных, а другая, кроме указанных независимых перемен­ных, имеет еще два (т. е. зависит от п+ 1переменных), строит функцию n независимых переменных. Один из дополнительных аргументов войдет вместе с аргументами первой функции в число аргументов вновь получаемой функции, а другой играет вспомогательную роль при выполнении оператора рекурсии. Оператор рекурсии будем обозначать Пр; его приме­нение будем записывать в виде строки: f = Пр(φ, ψ), где f означает получаемую функцию, φ — функцию п —1 независимых пе­ременных, ψ — функцию п+ 1независимых переменных.

При описании существа оператора рекурсии удобно не указывать ар­гументов первой из заданных функций ни в ее функциональной записи, ни в записях двух других функций, подразумевая эти аргументы. Тогда мож­но сказать, что оператор рекурсии задает функцию с помощью двух усло­вий, в которые входят функции φ и ψ. Алгоритм, сопутствующий операто­ру рекурсии, гласит: «Значением получаемой функции для нулевого зна­чения главного дополнительного аргумента считать значение исходной функции п -1 аргументов; значением определяемой функции для каждо­го последующего значения главного аргумента считать значение второй из заданных функций при предыдущем значении главного аргумента и при значении вспомогательного аргумента, совпадающем с предыдущим зна­чением определяемой функции».

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

1. f(x₁,x₂,…,x_n-1, 0) = φ(х₁,х₂,…,x_n-1).

2. f(x_1,x₂,…,x_n-1, y+1)= ψ(x_1,x₂,…,x_n-1, y,f(x_1,x₂,…,x_n-1, y)).

При этом, f(x_1,x₂,…,x_n-1, y+1)=C(ψ(x_1,x₂,…, y,x_n+1),f(x_1,x₂,…,x_n-1, y)).

Алгоритм построения примитивной рекурсии:

1. Выбираем две функции φ и ψ, у которых количество аргументов п-1 и п+1 соответственно;

2. Определяем значение для п-1 аргумента ификсируем значение х_п (п -го аргумента), это будет у;

3. Выбираем значение у=0;

4. Вычисляем f(x₁,x₂,…,x_n-1, 0) = φ(х₁,х₂,…,x_n-1);

5. Увеличиваем у на 1 и получаем функцию

ψ(x_1,x₂,…,x_n-1, y,f(x_1,x₂,…,x_n-1, y)) = f(x_1,x₂,…,x_n-1, y+1).

Правило примитивной рекурсии Если заданы две рекурсивные функции (φот п-1аргумена иψ от п+1 аргумента, то построенная с их помощьюпримитивная рекурсия даст тоже рекурсивную функцию.

Примеры: I. Доказать рекурсивность функции f(x,y)=x+y.

1. f(x,0)=x – рекурсивна, как базовая.

2. f(x,y+1)=x+(y+1)=x+y+1=z+1 – базовая, как функция следования.

z+1=ψ(x,y,z)= ψ(x,y,f(x,y))=(x+y)+1=x+(y+1)=f(x,y+1).

II. Доказать рекурсивность функции f(x,y)=x^y.

1. f(x,0)=x⁰=1=λ(0) – рекурсивна, как базовая.

2. f(x,y+1)=x^y+1=x^y ٠ x=z ٠ x – рекурсивная.

ψ(x,y,z)=x ٠ z; ψ(x,y, f(x,y))=z ٠ x= x^y ٠ x= x^y+1= f(x,y+1).

---

Дата добавления: 2015-07-11