Лекция 15.
Нерекурсивные функции
Нерекурсивной называется функция, значение которой нельзя вычислить, несмотря на то, что в данной рассматриваемой точке сама функция определена.
Например, зададим функцию f(x) следующим образом
 |
1 если м.Тьюринга Tx останавливается на чистой ленте
f(x)=
0 если м.Тьюринга Tx не останавливается на чистой ленте
Значения функции везде определены (0 или 1), но вычислены быть не могут, иначе это означало бы, что решена задача об остановке произвольной машины Тьюринга на чистой ленте, что противоречит теореме 1.5.(2).
Непримитивно рекурсивные функции
Непримитивно рекурсивной называется функция, являющаяся общерекурсивной, но не принадлежащая множеству примитивно-рекурсивных функций.
Одним из методов решения задачи о нахождении непримитивно рекурсивных функций может служить метод построения функции, растущей быстрее любой функции заданного класса. Этот метод очень удобен при исследовании сравнительной силы различного рода рекурсий. Изложим его применительно к уже рассмотренному классу примитивно рекурсивных функций.
Итак, нужно найти по возможности простые, но очень быстрорастущие функции. Опыт показывает, что произведение растет быстрее суммы, степень быстрее произведения. Называя сложение, умножение и возведение в степень действиями 0-й, 1-й и 2-й ступени и вводя для них в целях единообразия обозначения:
P0 (a, x)=a+x, P1 (a, x)=a∙x, P2(a, x)=ax,
приходим к знакомой всем идее о продолжении этой последовательности путем введения действий высших ступеней. При этом действие высшей ступени должно возникать из действия предыдущей ступени так же, как умножение возникает из сложения, а возведение в степень из умножения. Функции Р0, Р1, Р2 связаны следующими соотношениями:
P1(a, x+1)=P0(a, P1(a, x)), P1(a, 1)=a,
P2(a, x+1)=P1(a, P2(a, x)), P2(a, 1)=a.
Продолжим эту цепочку, полагая по определению для n=2, 3,…
Pn+1(a, 1)=a,
Pn+1(a, x+1)=Pn(a, Pn+1(a, x)).
Чтобы функции Pn(a, x) были определены всюду, положим Pn+1(a, 0)=1 при n=1, 2,… и указанные соотношения будем считать определениями функций Pn(a, x) для n=2, 3,… Ясно, что необходимо добавить соотношение P1(a,0)=0. Тогда, например,
P3(a, 0)=1, P3(a, 1)=a, P3(a, 2)=aa, P3(a, 3)=(aa)a.
Введем новые функции B(n, x)=Pn(2,x), A(x)=B(x, x).
Для функции B(n, x) из указанных соотношений вытекают следующие тождества:
В(n+1, x+1)=В(n, B(n+1, x))
B(n+1, 0) = sg n
B(0, x) = 2+x
Подобный способ возникновения рекурсивной функции B(n,x) из примитивно рекурсивных функций называется рекурсией второй ступени.
Можно определить функцию с подобными свойствами иначе, не прибегая к аналогии с возрастанием порядка операций от сложения к умножению, от умножения к степени и далее. Например, классическая функция Аккермана — относительно простой пример вычислимой функции, которая не является примитивно рекурсивной. Она принимает два неотрицательных целых числа в качестве параметров и в качестве своего значения возвращает натуральное число.
Функция Аккермана определяется рекурсивно для неотрицательных целых чисел m и n следующим образом:
А (0, n)= n +1
А (m, 0)= А (m -1, 1) при m >0
А (m, n)= А (m -1, А (m, n -1)) при m >0, n >0
Может показаться неочевидным, что рекурсия всегда заканчивается. Это следует из того, что при рекурсивном вызове или уменьшается значение m, или значение m сохраняется, но уменьшается значение n. Это означает, что каждый раз пара (m, n) уменьшается с точки зрения лексикографического порядка, значит, значение m в итоге достигнет нуля. Для одного значения m существует конечное число возможных значений n (так как первый вызов с данным m был произведён с каким-то определённым значением n, а в дальнейшем, если значение m сохраняется, значение n может только уменьшаться), а количество возможных значений m, в свою очередь, тоже конечно. Однако, при уменьшении m значение, на которое увеличивается n, обычно очень велико. Для того, чтобы почувствовать это, необходимо просто начать вычисление.
Внимательный читатель без проблем за несколько минут вычислит значение функции Аккермана в точке (2, 2), а потратив еще немного времени с использованием только карандаша и бумаги получит значение функции в точке (3, 3).
Интересно проследить рост значений этой функции, например, зафиксировав значение n =4.
А (0, 4) = 4+1 = 5
А (1, 4) = А (0, А (1, 3)) =
=А (0, А (0, А (1,2))) =
=А (0, А (0, А (0, А (1, 1)))) =
=А (0, А (0, А (0, А (0, А (1, 0))))) =
=А (0, А (0, А (0, А (0, А (0, 1))))) =
=А (0, А (0, А (0, А (0, 2)))) =
=А (0, А (0, А (0, 3))) =
=А (0, А (0, 4)) =
=А (0, 5) = 6
А (2, 4)= А (1, А (2, 3)) =
= А (1, А (1, А (2, 2))) =
= А (1, А (1, А (1, А (2, 1)))) =
= А (1, А (1, А (1, А (1, А (2, 0))))) =
= А (1, А (1, А (1, А (1, А (1, 1))))) =
…(здесь для ускорения процесса использованы предыдущие результаты, например, тот факт что А (1, 1) =3)…
= А (1, А (1, А (1, А (1, 3)))) =
= А (1, А (1, А (1, 5))) =
=продолжив далее, получим в итоге, что А (2, 4)=11
Аналогично можно вручную вычислить (это будет не очень быстро, но вполне реально)
А (3, 4)=125
Но дальше уже возникают сложности. С формальной точки зрения значение функции Аккермана всегда вычислимо – есть строгий, точный алгоритм, заканчивающийся за конечное число шагов. Однако получить численное значение в точке (4, 4) обычным способом вряд удастся. Эта функция растёт очень – очень быстро.
Аналитически можно выразить число А (4, 4) через степени числа 2:
Однако практически это вряд ли имеет смысл: это число настолько велико, что количество цифр в его порядке многократно превосходит количество атомов в наблюдаемой части вселенной. Задумайтесь над этим фактом и попробуйте представить, чему равно А (100, 4):