Частично–рекурсивные функции и тезис Черча
В силу узости класса примитивно–рекурсивных функций для определения алго- ритма необходимо выйти из этого класса. Мы рассмотрели оператор, применение которого выводит из класса примитивно–рекурсивных функций, — это оператор ми- нимизации. Будем использовать этот оператор как дополнительное конструктивное средство при определении нового класса функций.
Определение 2.6.Частично–рекурсивной называется функция, построенная из
простейших с помощью конечного числа операторов суперпозиции, примитивной ре- курсии и минимизации.
Определение 2.7.Всюду определенная частично–рекурсивная функция назы-
вается общерекурсивной или просто рекурсивной функцией.
В силу теоремы (2.10) примером рекурсивной, но не примитивно–рекурсивной функции является диагональная функция Аккермана A(x).
Частично–рекурсивные функции используются для определения понятия алго- ритма, которое вводится с помощью тезиса Черча.
Тезис Черча:всякий алгоритм может быть реализован частично–рекурсивной
функцией.
Понятие частично–рекурсивной функции — одно из главных в теории алгоритмов. Тезис Черча — это не теорема, а утверждение, которое связывает понятие алгорит- ма и строгое математическое понятие частично–рекурсивной функции. Тезис Черча является достаточным для того, чтобы придать необходимую точность формулиров- кам алгоритмических проблем и сделать принципиально возможным доказательство их неразрешимости. Утверждение о несуществовании частично–рекурсивной функ- ции эквивалентно факту несуществованию алгоритма решения соответствующей за- дачи.
В силу тезиса Черча вопрос о вычислимости функции или, что то же самое, о существовании алгоритма ее вычисления, равносилен вопросу о ее частичной ре- курсивности. Понятие частично–рекурсивной функции — строгое математическое, поэтому обычные математические методы и приемы позволяют непосредственно до- казать, что решающая задачу функция не может быть рекурсивной и тем самым доказать неразрешимость проблемы.
Точное описание класса частично–рекурсивных функций вместе с тезисом Чер- ча дает одно из возможных решений задачи о формальном определении алгоритма. Вместе с тем, это решение не вполне прямое, так как понятие вычислимой функ- ции является вторичным по отношению к понятию алгоритма: значение функции в каждой точке, соответствующей исходным данным алгоритма — это результат ра- боты алгоритма на этих данных. Спрашивается, нельзя ли уточнить само понятие алгоритма и уже затем при его помощи определить точно класс вычислимых функ- ций? Это было сделано Постом и Тьюрингом. Основная мысль, заложенная в такой формализации алгоритма, заключается в том, что алгоритмические процессы — это процессы, которые может совершать некоторая подходяще устроенная машина. В соответствии с этой мыслью в следующей главе мы рассмотрим описание в точ- ных математических терминах довольно узких классов машин, но на этих машинах оказывается возможным осуществить все алгоритмы. Алгоритмы, осуществимые на этих формально определенных машинах, можно рассматривать как математические точно определенные алгоритмы. В главе 3 мы покажем, что класс функций, вычис- лимых на этих машинах, в точности совпадает с классом всех частично–рекурсивных функций. Тем самым мы получим еще одно фундаментальное подтверждение тезиса
Черча.
Заметим, что хотя рассмотренный класс частично–рекурсивных функций содер- жит только функции, определенные на множестве натуральных чисел, это не снижа- ет общности представления об алгоритме как о частично–рекурсивной функции. Как мы рассмотрим в дальнейшем, существуют способы нумерации объектов, не являю- щихся по сути своей числами. В качестве простейшего примера приведем пока при- мер нумерации n–ок натуральных чисел ⟨a1, a2, . . . , an⟩. Для простоты рассмотрим сначала случай n = 2. В двумерном пространстве расположим пары натуральных чиел в виде следующей бесконечной матрицы:
< 0, 0 > < 0, 1 > → < 0, 2 > < 0, 3 > → < 0, 4 > . . .
↓ ↗ ↙ ↗ ↙
< 1, 0 > < 1, 1 > < 1, 2 > < 1, 3 > < 1, 4 > . . .
↙ ↗ ↙
< 2, 0 > < 2, 1 > < 2, 2 > < 2, 3 > < 2, 4 > . . .
↓ ↗ ↙
< 3, 0 > < 3, 1 > < 3, 2 > < 3, 3 > < 3, 4 > . . .
↙
< 4, 0 > < 4, 1 > < 4, 2 > < 4, 3 > < 4, 4 > . . .
↓
. . . . . . . . . . . . . . . . . .
Аналогично можно ввести нумерацию в n–мерном пространстве, нумеруя корте- жи ⟨a1, a2, . . . , an⟩.
Другой метод нумерации — метод цифр в некоторой системе счисления — основан на представлении объектов (не обязательно числовых ) в виде натурального числа в некоторой системе счисления с конечным основанием. Метод нумерации методом цифр мы рассмотрим в главе 3.
Контрольные вопросы к разделу
7. Перечислите свойства алгоритма. Какие из этих свойств являются обязатель- ными? Выполняются ли эти свойства для программ для ЭВМ?
8. Перечислите простейшие функции.
9. Дайте общее определение оператора примитивной рекурсии.
10. Запишите схему примитивной рекурсии для функции трех аргументов.
11. Дайте определение оператора суперпозиции.
12.Как устранить рекурсию в программе вычисления функции, если функция определена с помощью оператора примитивной рекурсии?
13. Может ли не всюду определенная функция быть примитивно-рекурсивной?
14. Дайте определение оператора минимизации.
15.В чем состоит отличие оператора минимизации от ограниченного оператора минимизации?
16. Какие цели преследовались при использовании ограничения в ограниченном операторе минимизации?
17. Пусть некоторая функция построена из примитивно-рекурсивных функций с помощью оператора минимизации. Является ли эта функция примитивно-рекурсив- ной?
18. Пусть некоторая функция построена из примитивно–рекурсивных функций с помощью ограниченного оператора минимизации. Является ли эта функция прими- тивно–рекурсивной?
19. Как строятся быстро растущие функции Pi(a, x)?
20. Поставьте знак отношения между B(n, x) и B(n + 1, x).
21. Поставьте знак отношения между B(n, x) и 2x.
22. Укажите зависимость между диагональной функцией Аккермана A(x) и функ- цией Аккермана B(n, x).
23. Какое отношение существует между множеством всех примитивно-рекурсив- ных функций и множеством всех частично-рекурсивных функций?
24. Является ли диагональная функция Аккермана примитивно-рекурсивной? Почему?
25. Сформулируйте тезис Черча.
26. Приведите формальное определение алгоритма.
Упражнения к разделу
Задачей выполнения упражнений является приобретение навыков даказательства примитивной или частичной рекурсивности заданной функции, усвоение принципов построения рекурсивного определения простых функций.
Задача 1
Доказать примитивную рекурсивность функции
f (x, y) = [log2(xy+2·x+ 2)].
Решение.Рассмотрим следующие вспомогательные функции:
g1(x, y) = x + y,
g2(x, y) = x · y, l
g3(x, y) = xy,
g4(x) = [log2(x + 1)].
Примитивную рекурсивность функции g1(x, y) = x + y мы доказали в 1.2. Докажем примитивную рекурсивность остальных функций. Рассмотрим сначала g2(x, y) = x · y. В соответствии с определением, некоторая функция является примитивно- рекурсивной, если выполняется одно из следующих условий:
а) эта функция является простейшей;
б) эта функция получена с помощью оператора примитивной рекурсии из функ- ций, примивная рекурсивность которых уже доказана;
в) эта функция получена с помощью оператора суперпозиции из функций, при- мивная рекурсивность которых уже доказана.
Попробуем построить схему примитивной рекурсии для функции g2(x, y). В соот-
ветствии с определением этой функции:
g2(x, 0) = x · 0 = 0 = 01(x);
g2(x, y + 1) = x · (y + 1) = x · y + x = g2(x, y) + x = g1(g2(x, y), x).
Покажем соответствие полученного рекурсивного определения функции g2(x, y) = x · y определению оператора примитивной рекурсии R и докажем примитивную ре- курсивность тех функций, из которых с помощью оператора R получена искомая функция. В соответсвии с определением, функция двух аргументов t(x, y) построена с помощью оператора R2(r, h), если она имеет вид:
t(x, 0) = r(x);
t(x, y + 1) = h(x, y, t(x, y)). (2.10)
Рассмотрим вид функций r(x) и h(x, y, z) в нашем случае:
g2(x, 0) = 01(x);
g2(x, y + 1) = g1(g2(x, y), x) = g1(I3(x, y, g2(x, y)), I3(x, y, g2(x, y)).
3 1
Таким образом, имеем
r(x) = 01(x),
h(x, y, z) = g1(I3(x, y, g2(x, y)), I3(x, y, g2(x, y)).
3 1
Суперпозиция примитивно–рекурсивных функций g1(x, y), I3(x, y, z), I3(x, y, z) при-
3 1
митивно рекурсивна, следовательно и функция g2(x, y) является примитивно–рекур-
сивной.
| In |
аргументы в том порядке, который соответствует схеме примитивной рекурсии. По- этому в дальнейшем не будем представлять функцию в форме, строго согласованной с порядком аргументов функции h(x,y,z) в (2.10). Например, для функции g3(x, y) имеем
g3(x, 0) = x0 = 1 = s(0(x));
g3(x, y + 1) = x(y + 1) = xy · y = g2(y, g3(x, y)).
Функция g3(x, y) получена оператором примитивной рекурсии из примитивно-рекур- сивных функций s(0(x)), g2(x, y) и, следовательно, примитивно-рекурсивна.
Доказательство для функции g4(x) = [log2(x+1)] выполняется с помощью ограни-
z+1
ченного оператора минимизации. Действительно, g4(x) = [log2(x+1)] = µz≤x+1(2 >
x+1), причем ограничивающая функция x+1 = s(x) и характеристическая функция
предиката
{ 0, 2z+1 ≤ x + 1
{0, 2z+1−˙(x + 1) = 0
z+1 ˙
χ(x, z) =
1, 2z+1 > x =
1, 2z+1−˙(x + 1) > 0 =sg(2
−(x + 1))
примитивно–рекурсивны. Следовательно, и g4(x) — примитивно–рекурсивная функ- ция.
Вернемся теперь к поставленной задаче доказательства примитивной рекурсив- ности функции
f (x, y) = [log2(xy+2·x + 2)] = g4(xy+2·x + 2 − 1) =
= g4(xy+2·x + 1) = g4(s(xy+2·x)) =
= g4(s(g2(x, y + 2 · x))) = g4(s(g2(x, g1(y, 2 · x)))) =
= g4(s(g2(x, g1(y, g1(x, x))))).
Функция f (x, y) является примитивно-рекурсивной как суперпозиция примитивно- рекурсивных функций.
Варианты заданий
1. f (x, y) = [log2((x + 1) · (yy+2x) + 2x] + 2 + [√y] .
2. f (x, y) = [x√3]+ [1+x+√yxy + 2x]+ 22x+y2.
...2y+2
3. f (x, y) = xyy+1 .
...2y+3
4. f (x, y) = x(y+1)(y+2) .
5. f (x) = [(x2+ x)√4 + x3+ 2x]+ [√5x3+ 2x + 1]+ 82x+2.
2x+3
6. f (x) =
∑ [√xi + 3i + ix + √2x + 2 + i] .
i=1
| y+2 |
8. f (x, y, z) = {x 3 } + [ 1+x+y xy + 2zy2] + 22x+z .
√ √ 2
9. f (x, y) = [x√4 + x2]+ [√5xy+ 2x + 1]+ 82x+y3.
10. f (x, y, z) = [(z2+ y)√4 + x3+ 2x = z4]+ [√3xz+ 2x + 1].
11. f (x, y) = [log5(yy+2·x) + x!] + [√x] + [√y] .
xx+4
i 3
| { }. |
∑ x+2 +i
4x+1+i
i=0
2x+3
13. f (x, y) =
∏ [√xi + 2i + 2y + √3y + i] .
i=1
14. f (x, y, z) =
x+z
∏
iy
| √ √ |
i=0 j=0
15. f (x) = [(x2+ y)√4 + x3+ 2x]+ [√5x3+ 2x + 1]+ 82x+2.
16. f (x) = [5x√2]+ [x+√2x + 2x4]+ 22x+2.
| y3+3 |
18. f (x, y) = [xy√x2+ y2]+ [1+√xxy + 2x]+ x2+y.
19. f (x) =
2x+3
∑
i=0
[xi+3i+ix ] 2x+2+i
| . |
| y2+2x |
Задача 2
Доказать примитивную рекурсивность функции p(x) – простое число с номером
x. В соответствии с доказательством написать программу вычисления этой функции.
Решение.Рассмотрим сначала вспомогательную функцию h(x), равную числу делителей числа x. Очевидная формула
x
h(x) = ∑(sg({x/i})),
i=1
(где выражение {x/i} означает остаток от деления x на i ) доказывает примитивную рекурсивность функции h(x), являющейся суперпозицией примитивно-рекурсивных функций. Простые числа и только они имеют ровно два делителя — единицу и самого себя. Числа 0 и 1 простыми не являются. Все числа, не являющиеся простыми, кроме 0 и 1, имеют число делителей, большее двух. Тогда характеристическая функция χp(x) предиката ⟨x — простое число при x > 1⟩ равна
χp(x) = sg(h(x)−˙2)
и является примитивно–рекурсивной.
Одной из наиболее известных арифметических функций является функция π(x), равная числу простых чисел, не превосходящих x. Используя уже известную нам примитивно–рекурсивную функцию χp(x), получим
x
π(x) = ∑(χp(i).
i=1
Отсюда следует, что искомая функция p(x) – простое число с номером x – представ- ляет собой минимальное решение уравнения
π(z) = x.
Таким образом,
p(x) = µz(π(z) = x).
Для доказательства примитивной рекурсивности функции p(x) достаточно ввести верхнюю границу изменения z и доказать примитивную рекурсивность как этой гра- ницы, так и характеристической функции предиката p(x) = x. Последнее легко сде- лать, т.к. эта функция равна
sg((π(z)−˙x) + (x−˙π(z))).
Осталось рассмотреть границу изменения z. Из теории чисел хорошо известно, что
n
pn< 22 . В самом деле, требующееся нам неравенство заведомо истинно при n = 0.
По индукции далее предполагаем, что это неравенство истинно для всех значений n, докажем его для n + 1.
Тогда
p0 < 22 ,
. . .
| n |
0 1 n
0 1 n
n+1
p0 · p1 · ... · pn + 1 < 22
· 22
· ... · 22
+ 1 = 22 +2 +...+2
+ 1 < 22 .
Число a = p0 · p1 · ... · pn+ 1 больше единицы и поэтому должно иметь какой-то про- стой делитель pr. Этот делитель не может совпадать ни с одним из простых чисел p0, p1, ...pn, так как при делении числа a на любое из чисел p0, p1, ...pnполучается остаток 1. Но все простые числа, не превосходящие pn, содержатся в последователь- ности p0 , p1 , ... pn. Число pr в нее не входит и, следовательно, pn+1 ≤ pr. Так как pr ≤ a, то
что и требовалось доказать.
pn+1 ≤ a < 22
n+1
,
Итак, неравенство доказано, а вместе с ним доказана и примитивная рекурсив- ность функции p(x), имеющей своим значением простое число с номером x.
Напишем теперь программу вычисления этой функции, соответствующую постро- енному доказательству. Сразу отметим, что доказательство примитивной рекурсив- ности функции не ставит своей целью построение алгоритма, обладающего хорошими временными характеристиками. Такое доказательство обосновывает лишь существо- вание алгоритма решения поставленной задачи, причем свойство определенности всюду для примитивно–рекурсивных функций означает, что для любых исходных данных соответствующая программа получит результат через некоторое конечное (может быть, очень большое ) время.
Приведенному выше доказательству соответствует следующая программа.
#include <stdio.h>
#include <STDLIB.H>
int sg(int x) { return x>0; }
int h(long int x)
{
long int i; int s=0;
for (i=1; i<=x; i++ ) 
i); return s;
}
int Xi(long int x)
{
if (x==1) return 1; if (x==0) return 0; return 1-sg(h(x)-2);
}
long int Pi( long int x)
{
long int i,s=0;
for (i=1; i<=x; i++ )s+=Xi(i); return s;
}
long int p( long int x)
{
long int z=0;
while (Pi(z)!=x) z++; return z;
}
void main(void)
{
int x; d",&x); unsigned long int z=p(x);
printf("простое число с номером dравно ld\n",x,z);
}
Следует отметить, что мы доказали алгоритм для любого x ∈ N . Однако, огра- ничение разрядной сетки компьютера не позволяет на уровне команд выполнить операции над сколь угодно большими числами. В нашей программе мы ограничили получаемые значения типом long int. Если программа должна работать с большими числами, необходимо реализовать так называемую длинную арифметику.
Варианты заданий
1. f (x) – количество ненулевых цифр в десятичной записи числа x.
2. f (x) – числитель следующего непрерывного многочлена x − − ой степени
1 + 1 .
1 + 1
1 + 1
1 + ... 1
1 +
x
Если в результате вычислений получается сократимая дробь, деление числителя и знаменателя на их наибольший общий делитель не выполнять.
3. f (x, y) – наименьшее общее кратное чисел x и y.
4. f (x, y) – минимальное простое число, принадлежащее отрезку [x, y].
5. f (x) – простое число с номером x; простые числа нумеровать, начиная от 0.
6. f (x) – количество ненулевых цифр в троичном представлении числа x.
7. f (x, y) – максимальное простое число, принадлежащее отрезку [x, y]. Если такие числа отсутствуют, значение функции равно 0.
8. f (x) – номер наибольшего простого делителя числа x, где f (0) = 0.
9. f (x) – количество единиц в шестнадцатиричном представлении числа x.
10. f (x, y) – число простых чисел, не превосходящих x + y.
11. f (x) – количество ненулевых цифр в шестнадцатиричном представлении за- данного числа x.
12. f (x) – произведение удвоенных делителей числа x.
13. f (x, y) – число простых чисел, не превосходящих x + y .
14. f (x) – нечетное число Фибоначчи с номером x. Числа Фибоначчи определя- ются следующим соотношением
F (0) = 0, F (1) = 1,
F (n) = F (n − 1) + F (n − 2) для n > 1.
Например, последовательность первых чисел Фибоначчи имеет вид:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...
15. f (x) – четное число Фибоначчи с номером n (см. пояснение к предшествую- щему упражнению ).
16.
| k |
четырехэлементного множества на две части:
{1, 2, 3} ∪ {4}, {1, 2, 4} ∪ {3}, {1, 3, 4} ∪ {2}, {2, 3, 4} ∪ {1},
{1, 2} ∪ {3, 4}, {1, 3} ∪ {2, 4}, {1, 4} ∪ {2.3}.
| k |
| k |
0 0
17.
| k |
| k |
| k |
произносится как "k циклов из n". Цикл [A, B, C, ..., D] равен циклу [B, C, ..., D, A], поскольку конец цикла соединен с его началом. Таким образом, для цикла из четырех элементов выполняется равенство
[A, B, C, D] = [B, C, D, A] = [C, D, A, B] = [D, A, B, C] .
Существует одиннадцать различных способов составить два цикла из четырех эле- ментов:
[1, 2, 3] [4] , [1, 2, 4] [3] , [1, 3, 4] [2] , [2, 3, 4] [1] ,
[1, 3, 2] [4] , [1, 4, 2] [3] , [1, 4, 3] [2] , [2, 4, 3] [1] ,
[1, 2] [3, 4] , [1, 3] [2, 4] , [1, 4] [2.3] .
18.
| k |
вок множества {1, 2, 3..., n}, имеющих k участков подъема, т.е. k мест в перестановке
ства {1, 2, 3, 4} (из всех 4! = 34 перестановок ) содержат по два участка подъема:
1324, 1423, 2314, 2413, 3412,
1243, 1342, 2341;
2134, 3124, 4123.
В первой строке перечислены перестановки с отношениями a1 < a2 > a3 < a4, во второй строке перечислены перестановки с отношениями a1 < a2 < a3 > a4, и в третьей – с отношениями a1 > a2 < a3 < a4.
19. f (x) – числитель несократимого гармонического числа с номером x. Гармони- ческим числом называется
1 1 1 n 1
∑
Hn = 1 + 2 + 3 + ... + n =
k
k=1
20. f (x) – знаменатель несократимого гармонического числа с номером x (см. пред- шествующее задание ).