Исторически первой алгоритмической системой была система, основанная на использовании конструктивно определяемых арифметических (целочисленных) функций, получивших специальное название рекурсивных функций.
На проблемном уровне рекурсия может быть определена как возможность алгоритмической системы на промежуточном этапе своего функционирования создавать другие системы, включая идентичные себе самой, и использовать результаты их функционирования в дальнейшей работе.
Глубина вложенности обращений системы к самой себе допускается сколь угодно большой.
Существуют разнообразные формы задания и проявления рекурсии.
В математике рекурсивные методы присутствуют практически во всех областях. Одно из классических математических определений алгоритма базируется на теории рекурсивных функций. Рекурсивные методы повсеместно используются в исследованиях по искусственному интеллекту, в программировании в вычислительных алгоритмах и в задачах проектирования сложных систем.
При достаточно широкой трактовке понятия алгоритмической системы концепция рекурсивности отражает основные формы развития материи и является одним из важнейших методов познания.
Наиболее ярко рекурсивность проявляется в процессе развития человека и человечества в целом. Информация, содержащаяся в клетке, кодирует информацию о всем организме. Дети «повторяют» своих родителей, а общество и материя развиваются по сложной рекурсивной спирали.
Хорошей иллюстрацией к сказанному могут служить следующие высказывания о рекурсии в природе: «В песчинке или капле, как в микрокосмосе, отражается общий состав космоса. В ней могут быть найдены все те же элементы, какие наблюдаются на земном шаре, в небесных пространствах…»( 1909г. В.И. Вернадский)
Или в стихотворении В.Я. Брюсова «Мир электрона» звучат те же мотивы:
« Быть может эти электроны –
Миры, где пять материков,
Искусства, знанья, войны, троны
И память сорока веков.
Еще быть может
Каждый атом-
Вселенная, где сто планет,
Там все, что здесь,
В объеме сжатом,
Но также то, чего здесь нет».
Рекурсия удобна для задания алгоритмов, а в некоторых случаях это единственно возможный способ определения сложного преобразования.
Понятие рекурсии необходимо разработчикам и пользователям сложных алгоритмических средств. Вместе с тем рекурсивные алгоритмы трудны в реализации и недостаточно исследованы теоретически.
В научной литературе приведено много результатов, посвященных рекурсии в программировании или в теории алгоритмов. Эта проблема является одной из наиболее «горячих точек» методологии программирования.
Дадим математическое определение рекурсии.
Рекурсией называется способ задания функции, при котором значение определяемой функции для произвольных значений аргументов выражается через значения определяемой функции для меньших значениях аргументов.
Численные функции, значение которых можно установить посредством алгоритма, называются вычислимыми функциями.
Функция называется рекурсивной, если существует эффективная процедура для ее вычисления.
Понятие эффективной процедуры является интуитивным. Говорят, что имеется эффективная процедура для выполнения определенных вычислений, если эти вычисления выполняются по механическим правилам, то есть по определенному алгоритму.
Поскольку понятие алгоритма в этом определении берется в интуитивном смысле, то и понятие вычислимой функции оказывается интуитивным.
Тем не менее, при переходе от алгоритмов к вычислимым функциям возникает одно очень существенное обстоятельство: совокупность процессов, подпадающих под понятие алгоритма очень обширна и мало обозрима. Совокупность вычислимых функций для самых разных пониманий процессов оказалась одной и той же и притом легко описываемой в обычных математических терминах.
Совокупность числовых функций, совпадающая с совокупностью всех вычислимых функций при самом широком понимании алгоритма, носит название совокупность рекурсивных функций.
В 1936г. математиком Чёрчем была сформулирована гипотеза о том, что класс рекурсивных функций тождественен классу всюду определенных вычислимых функций.
Эта гипотеза известна под именем тезиса Чёрча.
Понятие вычислимой функции точно не определяется, поэтому тезис Чёрча доказать нельзя. В дальнейших рассуждениях нам потребуются некоторые определения, которые введены ниже.
Если некоторым элементам массива Х поставить в соответствие однозначно определенные элементы множества У то говорят что задана частичная функция из Х в У.
Совокупность тех элементов множества Х у которых есть соответствующие элементы в У, называется областью определенности функции, а совокупность этих элементов множества У – совокупностью значений функции.
 |
|
Если область определенности функции из Х в У совпадает с множеством Х, то функция называется всюду определенной.
Клини ввел понятие частично рекурсивной функции и высказал гипотезу, что все частичные функции, вычислимые посредством алгоритмов, являются частично рекурсивными.
Эта гипотеза также недоказуема, как и гипотеза Чёрча, однако исследования последних лет выявили полную целесообразность считать понятие частично рекурсивной функции научным эквивалентом интуитивного понятия вычислимой частичной функции.
Тезис Чёрча оказался достаточным, чтобы придать необходимую точность формулировке алгоритмических проблем и в ряде случаев сделать возможным доказательство их неразрешимости.
Вопрос о вычислимости функции равносилен вопросу о ее рекурсивности. Понятие рекурсивной функции строгое, поэтому обычная математическая техника позволяет иногда непосредственно доказать, что решающая задачу функция не может быть рекурсивной, то есть задача неразрешима.
Применение рекурсивных функций в теории алгоритмов основано на идее нумерации слов в произвольном алфавите последовательными натуральными числами. Наиболее просто такую нумерацию можно осуществить, располагая слова в порядке возрастания их длин, а слова, имеющие одинаковую длину – в произвольном (лексикографическом) порядке.
После нумерации входных и выходных слов в произвольном алфавитном операторе, этот оператор превращается в функцию У=f(Х), в которой аргумент Х и функция У принимают неотрицательные целочисленные значения.
Функция f(Х) может быть определена не для всех значений Х, а лишь для тех, которые составляют область определения этой функции. Подобные частично определенные целочисленные и целозначные функции называются арифметическими функциями. Среди них выделим наиболее простые и будем их называть элементарными арифметическими функциями:
1.Функции тождественно равные нулю
On(x1,x2,…xn)=0 , (1)
определенные для всех неотрицательных значений аргументов;
2.Тождественные функции, повторяющие значения своих аргументов:
Ini(x1,x2,…xn)=xi (1<=i<=n, n=1,2,…) (2)
Частный случай I11(x)=x.
3.Функции непосредственного следования:
S1(x)=x для всех целых неотрицательных аргументов. (3)
Используя в качестве исходных функций элементарные, т.е. с помощью небольшого числа общих конструктивных приемов, можно строить все более и более сложные арифметические функции.
В теории рекурсивных функций очень важное значение имеют три операции:
-суперпозиции,
-примитивной рекурсии,
-наименьшего корня.
Операция суперпозиции функций заключается в подстановке одних арифметических функций вместо аргументов других рекурсивных функций.
Пусть заданы n функций f1,f2,…fn от m переменных и функция f((x1,x2,…xn) от n переменных.
Операция суперпозиции функций f1,f2,…fn с f даст функцию:
g(x1,x2,…xm) = f(f1(x1,x2,…xm),…. fn(x1,x2,…xm)).
Например, осуществляя операцию суперпозиции функций
f(x)=0 и g(x)=x+1, получим функцию h(x)=g)f(x))=0+1=1.
При суперпозиции g(x) с самой собой получим h(x)=x+2 и тому подобное.
Операция примитивной рекурсии позволяет строить (n+1) – местную арифметическую функцию (функцию от n+1 аргументов) по заданным двум функциям, одна из которых является n-местной, а другая (n+2)-местной.
Пусть заданы какие-нибудь частичные функции:
n-местная g и
(n+2)-местная h.
Говорят, что (n+1)-местная функция f возникает из функций g и h примитивной рекурсией, если для всех натуральных значений x1,x2,…xn,y имеем:
f(x1,x2,…xn,0) = g(x1,x2,…xn), (4)
f(x1,x2,…xm,y+1) = h(x1,x2,…xn,y,f(x1,x2,…xn,y)) (5)
Для правильного понимания примитивной рекурсии необходимо заметить, что всякую функцию от меньшего числа переменных можно рассматривать как функцию от любого большего числа переменных. В частности, функции - константы , которые естественно рассматривать как функцию от нуля аргументов, можно рассматривать как функцию от любого конечного числа аргументов.
В соответствии с этим операцию примитивной рекурсии будем применять и для n=0, говоря, что одноместная частичная функция f возникает примитивной рекурсией из постоянной одноместной функции, равной числу a и двуместной частичной функции h, если f(0)=a, f(x+1)=h(x,f(x)).
Встает вопрос, для каждых ли g и h существует функция f и будет ли она единственной? Область определения функции – множество всех натуральных чисел, поэтому ответ на оба вопроса – положительный.
Если f существует, то из (4) и (5) находим:
f(x1,x2,…xn,0)=g(x1,x2,…xn);
f(x1,x2,…xn,1)=h(x1,x2,…xn,0,g(x1,x2,…xm))
f(x1,x2,…xn,2)=h(x1,x2,…xn,1,f(x1,x2,…xn,1));
……..
f(x1,x2,…xn,m+1)=h(x1,x2,…xn,m,f(x1,x2,…xn,m))
и поэтому f определена однозначно.
Таким образом, для любых частичных n-местной функции g и (n+2)-местной функции h существует только одна частичная (n+1)-местная функция f, возникающая из g и h примитивной рекурсией.
Символически это записывается как: f=R(g,h).
Рассмотрим пример построения функции с использованием операции примитивной рекурсии:
Необходимо построить функцию суммирования f(x,y)=x+y.
Эта функция определяется с помощью тождественной функции g(x)=x и функции непосредственного следования h(x,y,z)=z+1.
Используя правила (4) и (5) имеем:
f(x,0)=g(x)=x;
f(x,1)=h(x,0,x)=x+1;
f(x,2)=h(x,1,x+1)=x+2;
f(x,y-1)=h(x,y-2,x+y-2)=x+y-1;
f(x,y)= h(x,y-2,x+y-1)=x+y.
Функции, которые могут быть построены из элементарных арифметических функций с помощью операций суперпозиции и примитивной рекурсии, примененных любое конечное число раз в произвольной последовательности, называется примитивно рекурсивными функциями.
Операции суперпозиции и примитивной рекурсии, будучи применимы к всюду определенным функциям, дают в результате снова всюду определенные функции.
В качестве примера докажем примитивную рекурсивность некоторых простых арифметических функций.
Двуместная функция f(x,y)=x+y удовлетворяет соотношениям:
(x+0)=x=I11(x) – тождественная функция;
x+(y+1)=(x+y)+1=S(x+y) – функция непосредственного следования.
Следовательно, функция x+y возникает из примитивно рекурсивных функций I11 и h(x,y,z)=z+1 операцией примитивной рекурсии и поэтому функция ( x+y) – примитивно рекурсивная.
Двуместная функция f(x,y)=x*y удовлетворяет схеме примитивной рекурсии:
x*0=O(x);
x*(y+1)=x*y+x с начальными примитивными функциями:
g(x)=O(x) и h(x,y,z)=z+x, поэтому функция x*y примитивно рекурсивная.
В области натуральных чисел разность (х-у) является определенной лишь для х>=y, так как отрицательные числа не входят в рассматриваемую область. Но примитивно рекурсивные функции всюду определены. Поэтому в теории примитивных рекурсивных функций вместо обычной разности вводят усеченную разность, обозначаемую -‘-, и определенную следующим образом:
0, x<y (6).
Примеры:
5 -‘- 3 = 2; 3-‘- 5 = 0 (x-‘-y)-‘-z = x-‘-(y+z)
Функция x-‘-1 удовлетворяет примитивно рекурсивной схеме:
0-‘-1 = 0
(x+1)-‘-1 = x
с примитивно рекурсивными начальными функциями O1, I21.
Поэтому функция x-‘-1 примитивно рекурсивная функция.
С другой стороны из (6) следует, что для любых x,y: x-‘-0 = x,
x-‘-(y+1) = (x-‘-y)-‘-1.
Эти тождества доказывают, что x-‘-y возникает примитивной рекурсией из функций I11 и h(x,y,z)=z-‘-1. Обе последние функции примитивно рекурсивные, следовательно, и функция (x-‘-y) - примитивно рекурсивная.
Большинство арифметических функций относятся к примитивно рекурсивным. Тем не менее, примитивно рекурсивные функции не охватывают всех арифметических функций, которые могут быть определены конструктивно. При построении всех этих функций используются другие операции, в частности операции наименьшего корня.
Операция наименьшего корня или операция минимизации позволяет определить новую арифметическую функцию 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.Какие бы классы точно очерченных алгоритмов до сих пор фактически не строились, во всех случаях неизменно оказывалось, что числовые функции, вычислимые посредством алгоритмов этих классов, были частично рекурсивными.
Поэтому общепринятой является следующая естественнонаучная гипотеза (тезис Чёрча):
Класс алгоритмических (или логических) вычисленных частичных числовых функций совпадает с классом всех частично рекурсивных функций.
Практически понятием частично рекурсивной функции пользуются для доказательства алгоритмической разрешимости или неразрешимости проблем. Использование же частично рекурсивной функции для представления того или иного конкретного алгоритма практически нецелесообразно ввиду сложности такого процесса алгоритмизации.
0 коммент.:
Отправить комментарий