В общем случае рекурсией называется такой способ задания функции, при котором значения определяемой функции для произвольных значений аргументов выражаются известным образом через значения определяемой функции для меньших значений аргументов.
Рассмотрим равенство f(х)=g(x), где f(х) и g(x) некоторые функции. Когда говорят, что это равенство есть уравнение, то это означает, что равенство рассматривается как неопределенное высказывание, при одних значениях х истинное, при других ложное.
Произвольная система рекурсивных уравнений задает частично – рекурсивную функцию. Если данная функция определена на всем множестве натуральных чисел, то она будет общерекурсивной. Также верно другое утверждение.Функция является общерекурсивной, если она определена посредством ряда уравнений некоторого типа.
Затруднение вызвано тем, что просмотр набора уравнений обычно не убеждает нас в том, что эти уравнения “определяют” какую-либо функцию вообще. Когда говорится “функция”, обычно понимается под этим “правило, которое каждому значению (или набору из п значений, если мы имеем функцию n переменных) ставит в соответствие результирующее значение”. Но в общем случае система уравнений не всегда дает определенное значение.
Например, система уравнений
Ф(x) +3x=f(x)
f(x+1)=f(x)+2
f(0)=3
задает некоторую функцию Ф(x). Однако ответить на вопрос, определяет ли данная система эту функцию Ф в общем случае невозможно. В данном конкретном случае такие выводы очевидно можно сделать на основе обычного подсчета значений и наших наблюдений касательно поведения функции при росте ее аргумента.
Таблица13.2.(1)
| x = | уравнение | f(x) | уравнение | Ф(x) |
| f(0)=3 | Ф(0)+0=3 | Ф(0)=3 | ||
| f(0+1)=f(0)+2=3+2=5 | f(1)=5 | Ф(1)+3*1=5 | Ф(1)=2 | |
| f(1+1)=f(1)+2=5+2=7 | f(2)=7 | Ф(2)+3*2=7 | Ф(2)=1 | |
| f(2+1)=f(2)+2=7+2=9 | f(3)=9 | Ф(3)+3*3=9 | Ф(3)=0 | |
| f(3+1)=f(3)+2=9+2=11 | f(4)=11 | Ф(4)+3*4=11 | Ф(4) не опред |
Из таблицы видно, что для значений x=4 и выше значение функции Ф не определено. Т.о. функция Ф(х) – частично-рекурсивная функция.
Т.о. вполне допустимой является ситуация, когда для некоторых (или даже для всех) точек значение функции не определено – считается, что в этих точках сама функция не определена. Это явление весьма характерно. Поэтому, делая предположение, что система уравнений действительно определяет общерекурсивную функцию, нужно всегда проявлять осторожность. Обычно требуется дополнительное доказательство этого положения, например, в виде индуктивного доказательства того, что для каждого значения аргумента вычисление завершается выдачей единственного значения.
Например, система уравнений
Ф(x) +x=f(x)
f(x+1)=f(x)+2
f(0)=3
задает функцию Ф(x), которая как видно из таблицы и наших наблюдений касательно поведения функции при росте ее аргумента, оказывается всюду определенной. Необходимо обратить особое внимание на то, что такой вывод мы может сделать только при рассмотрении конкретной заданной функции, в общем же случае, как будет показано позднее, невозможно придумать алгоритм, который на основе анализа системы рекурсивных уравнений некоторого типа сможет ответить на вопрос о принадлежности функции к классу общерекурсивных.
В данном случае вычисление значения функции Ф(х) дает следующие результаты (табл. 13.2.(2))
Таблица 13.2.(2)
| x= | уравнение | f(x) | уравнение | Ф(x) |
| f(0)=3 | Ф(0)+0=3 | Ф(0)=3 | ||
| f(0+1)=f(0)+2=3+2=5 | f(1)=5 | Ф(1)+ 1=5 | Ф(1)=4 | |
| f(1+1)=f(1)+2=5+2=7 | f(2)=7 | Ф(2)+ 2=7 | Ф(2)=5 | |
| f(2+1)=f(2)+2=7+2=9 | f(3)=9 | Ф(3)+ 3=9 | Ф(3)=6 | |
| f(3+1)=f(3)+2=9+2=11 | f(4)=11 | Ф(4)+ 4=11 | Ф(4)=7 |
Очевидно, что разница между значением функции f(x) и собственно значением аргумента х с ростом аргумента только увеличивается, а значит уравнение Ф(x) +x=f(x) всегда будет иметь единственное решение. Т.о. функция Ф(х) – общерекурсивная функция.
Система уравнений может быть задана через базисные операции в виде схемы рекурсии. Например, рассмотрим систему уравнений, задающую функцию F(x):
E(x)=R0(U21)
F(x)=E-1(x)
Если раскрыть операции рекурсии и обращения функций, получим:
 |
E(0)=0
E(x+1)=E(x)
F(x)=my[E(y)= x]
Для х=0 значение F(x) определено и равно 0. Но для х=1 наше определение “не работает”, так как выражение F(1)=my[E(y)=1], означает:
-сначала посмотри, истинно ли Е(0) = 1;
-если нет, посмотри, истинно ли Е(1) = 1;
-если нет, посмотри, истинно ли Е(2) = 1;
-если нет, то... и т.д.
Вычисление никогда не заканчивается, потому что Е(х) всегда равна нулю, и для F(1) не будет найдено никакого значения.
Вследствие этого при рассмотрении функций, заданных системами рекурсивных уравнений, будем обычно говорить о частично-рекурсивной функции. Когда говорится о частично-рекурсивной функции F(x), то надо понимать, что может не существовать значения, определенного для некоторого (или даже любого!) значения х. Если F(x) о казывается определенной для всех значений х, то будем называть ее общерекурсивной функцией. Конечно, любая общерекурсивная функция также является частично-рекурсивной.