Исторически первой алгоритмической системой была система, основанная на использовании конструктивно определяемых арифметических (целочисленных) функций, получивших специальное название рекурсивных функций.
Рекурсией называется способ задания функции, при котором значение определяемой функции для произвольных значений, аргументов выражается известным образом через значения определяемой функции для меньших значений аргументов.
Численные функции, значение которых можно установить посредством некоторого алгоритма, называются вычислимыми функциями. Функция называется рекурсивной, если существует эффективная процедура для ее вычисления. Понятие эффективной процедуры является интуитивным. Говорят, что имеется эффективная
процедура для выполнения определенных вычислений, если эти вычисления выполняются по механическим правилам, т. е. по определенному алгоритму.
Поскольку понятие алгоритма в этом определении берется в интуитивном смысле, то и понятие вычислимой функции оказывается интуитивным. Тем не менее при переходе от алгоритмов к вычислимым функциям возникает одно очень существенное обстоятельство: совокупность процессов, подпадающих под интуитивное понятие алгоритма, очень обширна и мало обозрима. Совокупность
вычислимых функций для самых разных понимании процессов оказалась одной и той же и притом легко описываемой в обычных математических терминах.
Совокупность числовых функций, совпадающая с совокупностью всех вычислимых функций при самом широком до сих пор известном понимании алгоритма, носит название совокупности рекурсивных функций.
Гёдель впервые описал класс всех рекурсивных функций как класс всех числовых функций, определимых в некоторой формальной системе. Исходя из совершенно других предпосылок, Черч в 1936 г. вывел тот же класс числовых функций, что и Гёдель.
Черчем была сформулирована гипотеза о том, что класс рекурсивных функций тождествен с классом всюду определенных вычислимых функций. Эта гипотеза известна под именем тезиса Черча.
Понятие вычислимой функции точно не определяется, поэтому тезис Черча доказать нельзя.
Если некоторым элементам множества Х поставлены в соответствие однозначно определенные элементы множества Y, то говорят, что задана частичная функция из Х в Y.
Совокупность тех элементов множества X, у которых есть соответствующие в Y, называется областью определенности функции, а совокупность этих элементов множества Y—совокупностью значений функции. Если область определенности функции из Х в Y совпадает с множеством X, то функция называется всюду определенной.
Клини ввел понятие частично рекурсивной функции и высказал гипотезу, что все частичные функции, вычислимые посредством алгоритмов, являются частично рекурсивными. Эта гипотеза также недоказуема, как и гипотеза Черча. Однако математические исследования последних 30 лет выявили полную целесообразность
считать понятие частично рекурсивной функции научным эквивалентом интуитивного понятия вычислимой частичной функции.
В дальнейшем под тезисом Черча будем понимать гипотезу Черча в том расширенном виде, который был придан ей Клини. Тезис Черча оказался достаточным, чтобы придать необходимую точность формулировке алгоритмических проблем и в ряде случаев сделать возможным доказательство их неразрешимости.
В силу тезиса Черча вопрос о вычислимости функции равносилен вопросу о ее рекурсивности. Понятие рекурсивной функции строгое. Поэтому обычная математическая техника позволяет иногда непосредственно доказать, что решающая задачу функция не может быть рекурсивной, т. е. задача неразрешима.
Применение рекурсивных функций в теории алгоритмов основано на идее нумерации слов в произвольном алфавите последовательными натуральными числами. Наиболее просто такую нумерацию можно осуществить, располагая слова в порядке возрастания их длин, а слова, имеющие одинаковую длину, — в произвольном (лексикографическом) порядке.
После нумерации входных и выходных слов в произвольном алфавитном операторе этот оператор превращается в функцию у = f{х), в которой аргумент х и функция у принимают неотрицательные целочисленные значения. Функция f(х) может быть определена не для всех значении х, а лишь для тех, которые составляют область определения этой функции.
Подобные частично определенные целочисленные и целозначные функции для краткости называются арифметическими функциями, среди них выделим наиболее простые и будем их называть элементарными арифметическими функциями:
1) функции, тождественно равные нулю:
Оn(х1,х2,…,хn)=0,
определенные для всех неотрицательных значений аргументов;
2) тождественные функции, повторяющие значения своих аргументов:
I(х1,х2,…,хn) = хi (1=< i =< n; n = 1, 2,…), частный
случай I(х) == х;
3) функции непосредственного следования:
S1( х ) = х+1
также определенные для всех целых неотрицательных значений своего аргумента.
Используя в качестве исходных функций перечисленные элементарные арифметические функции, можно с помощью небольшого числа общих конструктивных приемов строить все более и более сложные арифметические функции. В теории рекурсивных функций особо важное значение имеют три операции: суперпозиции, примитивной рекурсии и наименьшего корня. Рассмотрим каждую из них.
Операция суперпозиции функций заключается в подстановке одних арифметических функций вместо аргументов других арифметических функций.
Пусть заданы n функций f1, …,fn от m переменных каждая и функция f(х1,…, xn) от n переменных. Операция суперпозиции функций f1, …,fn с f даст нам функцию
g(x1,…,xm)=f(f1(x1,…,xm),…,fn(x1,…,xm)).
Например, осуществляя операцию суперпозиции функций f(х) = 0 и g(х) == х + 1, получим функцию
h(x)=g(f(x))=0+1=1.
При суперпозиции функции g(х) с самой собой получим функцию g{х) = х + 2 и т. п.
Операция суперпозиции обозначается символом 5″+1, где индекс сверху означает число функций.
Операция примитивной рекурсии позволяет строить n + 1-местную арифметическую функцию (функцию от n + 1 аргумента) по двум заданным функциям, одна из которых является n-местной, а другая n + 2-местной.
Пусть заданы какие-нибудь числовые частичные функции: n-местная g и n + 2-местная h. Говорят, что n + 1-местная частичная функция f возникает из функций g и h примитивной рекурсией, если для всех натуральных значений x1, …, xn, у имеем:
f(x1,…,xn,0)=g(x1,…,xn); (3)
f(x1,…,xn,y+1)=h(x1,…,xn,y,f(x1,…,xn,y)).(4)
Для правильного понимания операции примитивной рекурсии необходимо заметить, что всякую функцию от меньшего числа переменных можно рассматривать как функцию от любого большего числа переменных. В частности, функции-константы, которые естественно рассматривать как функции от нуля аргументов, можно рассматривать как функции от любого конечного числа аргументов.
В соответствии с этим операцию примитивной рекурсии будем применять и для n == 0, говоря, что одноместная частичная функция f возникает примитивной рекурсией из постоянной одноместной функции, равной числу а, и двуместной частичной функции h, если
f(0)=а;
f(x+1)=h(x, f(x)).
Встает вопрос, для каждых ли g и h существует функция f и будет .ли она единственной. Область определения функции — множество всех натуральных чисел, поэтому ответ на оба вопроса положительный.
Если f существует, то из (3) и (4) находим:
f(x1,…,xn,0)=g(x1,…,xn)
f(x1,…,xn,1)=h(x1,…,xn,0, g(x1,…,xn))
f(x1,…,xn,2)=h(x1,…,xn,1,f(x1,…,xn,1))
……………………………..
f(x1,…,xn,m+1)=h(x1,…,xn,m,f(x1,…,xn,m))
и поэтому f определена однозначно. Таким образом, для любых частичных n-местной функции g и n + 2-местной функции h/n = 0, 1, 2, … существует только одна частичная n + 1-местная функция f, возникающая из g и h примитивной рекурсией. Символически пишут f=R(g,h).
Из (5) видно что если мы каким-то образом умеем находить значение g и h, то значение f можно вычислить при помощи процедуры вполне механического характера. Для нахождения значения f (a1,…,an,m+1) достаточно последовательно найти числа:
b0=g(a1,…,an)
b1=h(a1,…,an,0,b0)
b2=h(a1,…,an,1,b1)
…………………….
bm+1=h(a1,…an,m,bm)
Полученное на m+1 шаге число bm+1 и будет искомым значением f в точке (a1,…,an,m+1).
Функции, которые могут быть построены из элементарных арифметических функций с помощью операций суперпозиции и примитивной рекурсии, примененных любое количество раз в произвольной последовательности, называются примитивно рекурсивными функциями.
Операции суперпозиции и примитивной рекурсии, будучи применены к всюду определенным функциям, дают в результате снова всюду определенные функции.
Большинство арифметических функций относятся к примитивно рекурсивным. Тем не менее примитивно рекурсивные функции не охватывают всех арифметических функций, которые могут быть определены конструктивно. При построении всех этих функций используются другие операции, в частности операция наименьшего корня.
Операция наименьшего корня, или операция минимизации, позволяет определить новую арифметическую функцию f(x1,…,xn) от n переменных с помощью ранее построенной арифметической функции g(x1,…,xn,y) от n+1 переменных.
Для любого заданного набора значений переменных x1=a1,…,xn=an в качестве соответствующего значения f(a1,…,an) определяемой функции f(x1,…,xn) принимается наименьший целый неотрицательный корень y=a уравнения g(a1,…an,y)=0.
В случае несуществования целых неотрицательных корней у этого уравнения функция f(x1,…,xn) считается неопределенной при соответствующем наборе значений переменных.
Арифметические функции, которые могут быть построены из элементарных арифметических функций с помощью операций суперпозиции, примитивной рекурсии и наименьшего корня, называются частично рекурсивными функциями. Если такие функции оказываются к тому же всюду определенными, то они называются общерекурсивными функциями.
В этом определении, как и определении примитивно рекурсивных функций, предусматривается возможность выполнения всех допустимых операций в любой последовательности и в любое конечное число раз.
Частично рекурсивные функции представляют собой наиболее общий класс конструктивно определяемых арифметических функций.
Понятие частично рекурсивной функции — одно из главных понятий теории алгоритмов. Значение его состоит в следующем.
1. Каждая стандартно заданная частично рекурсивная функция вычислима путем определенной процедуры механического характера.
2. Какие бы классы точно очерченных алгоритмов до сих пор фактически не строились, во всех случаях неизменно оказывалось, что числовые функции, вычислимые посредством алгоритмов этих классов, были частично рекурсивными. Поэтому общепринятой является следующая естественнонаучная гипотеза, известная под именем тезиса Черча.
Класс алгоритмически ( или машинно ) вычислимых частичных числовых функций совпадает с классом всех частично рекурсивных функций. Этот тезис дает алгоритмическое толкование понятию частично рекурсивных функций.
Практически понятием частично рекурсивных функций пользуются для доказательства алгоритмической разрешимости или неразрешимости проблем.
Использование же частично рекурсивных функций для представления того или иного конкретного алгоритма практически нецелесообразно ввиду сложности такого процесса алгоритмизации.