A08DPPMAT_UPS2006D00

Оператор примитивной рекурсии R. Рассмотрим действие, которое назовем оператором примитивной рекурсии. С помощью оператора примитивной рекурсии мы конструируем функцию f от n 1 переменной из некоторых частичных функций g и h. При этом функция g имеет n 0 переменных, а функция h имеет n 2 переменных. Значения новой функции f вычисляем по двум правилам:

f x1, x2, . . . , xn, 0	g x1, x2, . . . , xn ,	(3.7)
f x1, x2, . . . , xn, y 1	h x1, x2, . . . , xn, y, f x1, x2, . . . , xn, y .	(3.8)

Слово рекурсия (recurso на латинском языке — возвращаюсь) означает вычисление значения f x1, x2, . . . , xn, y 1 с использованием f x1, x2, . . . , xn, y (возвращением к ранее вычисленному значению). Из (3.7) и (3.8) получаем последовательное вычисление значений функции f :

f x1, x2, . . . , xn, 0	g x1, x2, . . . , xn ,
f x1, x2, . . . , xn, 1	h x1, x2, . . . , xn, 0, f x1, x2, . . . , xn, 0 , (3.9)
	. . .
f x1, x2, . . . , xn, m 1	h x1, x2, . . . , xn, m, f x1, x2, . . . , xn, m .

Если все значения в правых частях равенств существуют, то получим значение функции f x1, x2, . . . , xn, m 1 . Если какое-то значение не определено, то f x1, x2, . . . , xn, m 1 не существует. Поэтому в общем случае мы получаем частичную функцию f x1, x2, . . . , xn 1 от n 1 переменной.

В случае n 0 функция g из (3.7) имеет 0 переменных и поэтому отождествляется с некоторым числом a. Тогда равенство (3.7) имеет вид

f x1, x2, . . . , xn, 0 a.

Если функция f получена оператором примитивной рекурсии из функций g и h (т.е. задана правилами (3.7) и (3.8)), то записываем

f R g, h .

(3.10)

Как и в случае оператора суперпозиции, вычислимость исходных функций g и h влечет вычислимость построенной из них функции f .

ОПРЕДЕЛЕНИЕ 3.1 . Функция f называется примитивно рекурсивной, если она может быть получена из простейших функ-

ций s x x 1, on x1, x2, . . . , xn 0, Imn x1, x2, . . . , xn xm

с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.

21

Тоже самое можно выразить в виде трех правил. 1 Простейшие функции

s x x 1, on x1, x2, . . . , xn 0, Imn x1, x2, . . . , xn xm

примитивно рекурсивны.

2 Если функция f получена из примитивно рекурсивных функций с помощью оператора суперпозиции или с помощью оператора примитивной рекурсии, то функция f примитивно рекурсивна.

3 То, что функция f примитивно рекурсивна, устанавливается несколькими применениями правил 1 и 2 .

Можно представить следующий процесс. В некотором ящике первоначально находятся простейшие функции s x , on x1, x2, . . . , xn , Imn x1, x2, . . . , xn . Эти функции назовем примитивно рекурсивными функциями, полученными на шаге 0. Возьмем некоторые функции, полученные на шаге 0, и применим к ним один из операторов суперпозиции или примитивной рекурсии. Получится примитивно рекурсивная функция f шага 1, которую также поместим в данный ящик. Повторяем всевозможные действия данного типа, и пополняем ящик. Функция f примитивно рекурсивна, если она попадет в ящик на некотором шаге данного процесса.

Всякой примитивной рекурсивной функции можно приписать n — наименьший номер шага, на котором она может быть получена.

При этом простейшие функции s x x 1, on x1, x2, . . . , xn 0, Imn x1, x2, . . . , xn — частично рекурсивные функции шага 0. Следова-

тельно, можно проводить доказательство различных утверждений для примитивно рекурсивных функций индукцией по шагу, на котором они получены.

Рассмотрим простые примеры примитивно рекурсивных функций.

ПРЕДЛОЖЕНИЕ 3.2. Функция f x x примитивно рекурсивна.

Доказательство. Функция проектирования Imn			x1, x2, . . . , xn		xm
примитивно рекурсивна. Рассмотрим случай n			1 и m	1. Имеем
I11 x1	x1. Заменим обозначение I11 на f , а переменную x1 обозначим
через x. Получим функцию f x		x. Итак, функция f x			x — это
функция проектирования при n		1 и m 1. Поэтому она примитивно
рекурсивна.
Предложение доказано.

22

ПРЕДЛОЖЕНИЕ 3.3. Функция g x x 2 примитивно рекурсивна.

Доказательство. Рассмотрим функцию f x x. Тогда

g x x 2 x 1 1 s s x , т.е. g x s s f x .

Функция f x x примитивно рекурсивна по предыдущему предложению. Функция следования s x x 1 примитивно рекурсивна, т.к. является простейшей функцией.

К примитивно рекурсивным функция s x и f x применим оператор суперпозиции. Получим примитивно рекурсивную функцию s f x . Повторно применим оператор суперпозиции к функциям s x и s f x . Получим примитивную рекурсивность функции s s f x , что и нужно.

Предложение доказано.

ПРЕДЛОЖЕНИЕ 3.4 . Постоянная унарная функция f x	a
примитивно рекурсивна.
Доказательство. Имеем запись
f x s s . . . s o x a,
a раз

где функции s x и o x — простейшие функции. Применяя оператор суперпозиции несколько раз, получим что функция f x a примитивно рекурсивна.

ПРЕДЛОЖЕНИЕ 3.5. Нульарная функция примитивно рекурсивна.

Доказательство. Пусть f — нульарная функция, значения которой равны a. Нульарная нулевая функция g o0 имеет 0 переменных и отождествляется с числом 0 N. Она примитивно рекурсивна, т.к. является простейшей функцией. В следующем равенстве функция следования s повторена a раз, т.е. a раз применен оператор суперпозиции

s s . . . s g a.

(3.11)

a

Следовательно, функция в левой части (3.11) примитивно рекурсивна. Она имеет 0 переменных и тождественно равна a. Эта функция является

23

нульарной функцией f , примитивную рекурсивность которой нам требовалось установить. Предложение доказано.

Операция введения фиктивных переменных. Рассмотрим функцию f x, y x y. Функция f является функцией от двух переменных. Пусть z переменная, отличная от x и y. Рассмотрим функцию f x y z z от трех переменных. Значения новой функции f не зависят от ее переменной z. Такую переменную будем называть фиктивной переменной. По замечанию 2.1 функции f и f — различные функции, т.к. имеют различное число переменных. С другой стороны, имеется равенство f x, y, z f x, y . Мы будем говорить, что функция f получена из функции f введением фиктивной переменной z. Проверим в общем случае, что примитивная рекурсивность функции f влечет примитивную рекурсивность функции f , полученной введением фиктивной переменной.

Пусть функция f f x1, . . . , xn примитивно рекурсивна. Добавим в строке переменных x1, . . . , xn еще одну переменную xn 1. Получим строку x x1, . . . , xn 1 из n 1 переменной. Для функций проектирования очевидны n равенств

I1n 1 x x1, . . . , Inn 1 x xn.

Введем функцию f x от n 1 переменной правилом

f x1, . . . , xn, xn 1 f I1n 1 x , . . . , Inn 1 x f x1, x2, . . . , xn .

Так как функция f примитивно рекурсивна, то и новая функция f примитивно рекурсивна.

В дальнейшем мы будем вводить фиктивную переменную, и из примитивно рекурсивной функции от n переменных получать примитивно рекурсивную функцию от n 1 переменной. При такой операции введения фиктивного переменной вместо обозначения f для новой функции будем сохранять обозначение f исходной функции.

ПРЕДЛОЖЕНИЕ 3.6 . Функция сложения f x, y x y примитивно рекурсивна.

Доказательство. Покажем, что функция сложения f x, y может быть получена с помощью оператора примитивной рекурсии из двух функций g x и h x, y, z , для которых примитивная рекурсивность уже установлена. Способ для подбора функций g и h в общем случае состоит в выполнении двух действий.

24

1) Применим правило (3.7), т.е. равенство

f x1, x2, . . . , xn, 0 g x1, x2, . . . , xn ,

иполучим функцию g.

2)Применим правило (3.8), т.е. равенство

f x1, x2, . . . , xn, y 1 h x1, x2, . . . , xn, y, f x1, x2, . . . , xn, y ,

и получим функцию h.

В нашем случае n	1 и f x, y x y .
1) Имеем g x	f x, 0 x 0 x. Получили искомую функцию

g x x. То, что функция g x примитивно рекурсивна, уже известно по предложению 3.2.

2) Подберем функцию h x, y, z . Применим правило (3.8) для функции f x, y x y. Получим равенства

f x, y 1 x y 1 x y 1 s x y s f x, y h x, y, f x, y .

При этом h x, y, z s z . Функция h x, y, z получена из примитивно рекурсивной функции s z введением двух фиктивных переменных x и y. Поэтому функция h x, y, z примитивно рекурсивна. Получили, что функция f x, y x y примитивно рекурсивна.

Предложение доказано.

ПРЕДЛОЖЕНИЕ 3.7. Функция умножения f x, y xy примитивно рекурсивна.

Доказательство. Как и в предыдущем предложении подберем функции g x и h x, y, z , применяя правила (3.7) и (3.8).

Имеем g x f x, 0 x 0 0. Поэтому g x — нулевая функция o x , которая примитивно рекурсивна.

Покажем, что в качестве искомой функции h x, y, z можно взять функцию h x, y, z x z, которая примитивно рекурсивна, т.к. получена из функции сложения введением фиктивной переменной y. Имеем

f x, y 1 x y 1 x xy x z при z xy f x, y .

Тогда f x, y 1 h x, y, f x, y . Из примитивной рекурсивности функций g x и h x, y, z заключаем, что функция f x, y xy примитивно рекурсивна.

Предложение доказано.

25

Упражнения к лекции 3

ЗАДАЧА 1. Пусть n N. Доказать примитивную рекурсивность функции f x x n.

ЗАДАЧА 2. Доказать, что всякая примитивно рекурсивная функция является всюду определенной функцией.

ЗАДАЧА 3. Пусть n — произвольное натуральное число. Доказать примитивную рекурсивность следующих функций

1 f x, y	x y 1,	2 f x, y	xy 2,	3 f x	nx,
4 f x, y	xy где 00	1 , 5 f x	x2,	6 f x	xn.

ЗАДАЧА 4. Доказать, что следующие функции примитивно рекурсивны

1 sg x

0, если x

0,

2

x 1, если x 0,

sg

1, если x 0.

0, если x 0.

3 x 1

0,

если x 0,

4 x

y

0,

если x y,

x

1, если x 0.

x

y,

если x y.

ЗАДАЧА 5. Проверить равенство

x

y

x

y y x ,

и доказать,что функция f x, y

x

y примитивно рекурсив-

на.

ЗАДАЧА 6. Проверить равенство

max x, y

x sg x

y y

x

y ,

sg

и доказать, что функция f x, y

max x, y примитивно рекурсив-

на.

ЗАДАЧА 7. Проверить равенство

min x, y

x sg y

x y

y

x ,

sg

и доказать, что функция f x, y

min x, y примитивно рекурсив-

на.

26

ЗАДАЧА 8. Функция f получена из функций g и h с помощью оператора примитивной рекурсии. Указать формулу для вычисления функции f .

1 g x	x,	h x, y, z	z 1,	f x, y ?
2 g x	0,	h x, y, z	x z,	f x, y ?
3 g x	1,	h x, y, z	xz,	f x, y ?
4 g o0,		h x, y y,		f x ?

При этом функция g из пункта 4 является нульарной функцией, равной 0.

ЗАДАЧА 9. Доказать, что функция следования s x не может быть получена из нулевых функций и функций проектирования с помощью операторов суперпозиции и примитивной рекурсии.

Указание. Пусть функция f x1, . . . , xn получена из нулевых

функций и	функций	проектирования с помощью операто-
ров суперпозиции и		примитивной рекурсии. Проверить, что
f 0, . . . , 0	0.

ЗАДАЧА 10. Пусть даны n-арные функции α1, . . . , αk со следующим условием. Для любого набора переменных x1, . . . , xn одна и только одна из этих функций равна 0. Скажем, что функция f x1, . . . , xn кусочно задана через эти функции, если

		g1		x1, . . . , xn ,	если α1 x1, . . . , xn	0,
	f x1	, . . . , xn	g2	x1, . . . , xn ,	если α2 x1, . . . , xn	0,
			. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
		gk x1, . . . , xn ,			если αk x1, . . . , xn	0.

Доказать, что если функции g1, . . . , gk, α1, . . . , αk примитивно рекурсивны, то функция f примитивно рекурсивна.

Указание. Проверить равенство

f x1, . . . , xn g1 x1, . . . , xn sg α1 x1, . . . , xn . . .

gk x1, . . . , xn sg αk x1, . . . , xn .

27

Лекция 4. Частично рекурсивные функции. Тезис Черча

Оператор минимизации M. Пусть дана вычислимая функция g x1, . . . , xn, y от n 1 переменной, где n 0. Нам нужно найти наименьшее число y с условием g x1, . . . , xn, y 0. Введем следующее ограничение. Процедура нахождения числа y должна быть алгоритмом. Поэтому должен быть представлен точный список действий для неинтеллектуального исполнителя (машины) по нахождению y, например, последовательная проверка одного за другим следующих равенств

f x1, x2, . . . , xn, 0	0,
f x1, x2, . . . , xn, 1	0,	(4.1)
. . .
f x1, x2, . . . , xn, y	0,
. . .

Что при этом произойдет? Возможно, вообще нет числа y с условием f x1, x2, . . . , xn, y 0. Тогда не произойдет остановки машины с выдачей y. Однако отсутствие y возможно по другой причине. Предположим,

например, что f x1, x2, . . . , xn, 5 0, а значение f x1, x2, . . . , xn, 2 не определено. Пытаясь вычислить f x1, x2, . . . , xn, 2 , машина будет рабо-

тать бесконечно и никогда не перейдет к вычислению f x1, x2, . . . , xn, 3 . Поэтому число y 5 не будет обнаружено.

ОПРЕДЕЛЕНИЕ 4.1 . Пусть g — функция от n 1 переменной. Функция f от n переменных получена из функции g с помощью оператора минимизации, если равенство f x1, x2, . . . , xn y верно тогда и только тогда, когда f x1, x2, . . . , xn, y 0, а значения

f x1, x2, . . . , xn, 0 , . . . , f x1, x2, . . . , xn, y 1 определены и не равны нулю.

Тоже самое можно выразить записью
	f x1, x2,..... . , xn, 0 0 ,
f x1, x2, . . . , xn y	f x1, x2, . . . , xn, y	1 0,
	f x1, x2, . . . , xn, y	0,

причем значения f x1, x2, . . . , xn, 0 , . . . , f x1, x2, . . . , xn, y существуют.

28

Если функция f получается из функции g с помощью оператора минимизации, то записываем

f M g .

(4.2)

Ясно, что инструкции для вычисления функции g и проверки (4.1) образуют алгоритм для вычисления значений функции f . Поэтому функция f вычислима.

ПРИМЕР 4.1. Найти функцию f , полученную из функции o x применением оператора минимизации.

Решение. Если функция f получена из функции g с помощью оператора минимизации, то число ее переменных меньше числа переменных функции g на единицу. В данном случае g— это функция o x от одной переменной. Поэтому функция f имеет 0 переменных.

Для нахождения значения функции f нужно проверить условия

o 0 0, o 1 0, . . . , o y 0, . . .

и выбрать в этих равенствах наименьшее y. Поскольку o x 0 для всех x, то наименьшее число y — это y 0. По определению оператора минимизации полученное y 0 и есть значение функции f .

Поэтому функция f — это нульарная функция o0 со значением 0, т.е. помеченный элемент 0.

Сформулируем теперь одно из основных определений теории алгоритмов — определение частично рекурсивной функции.

ОПРЕДЕЛЕНИЕ 4.2. Функция f называется частично рекурсивной функцией, если она может быть получена из следующих простейших функций:

1 функции следования s x x 1,

2 нулевой функции on x1, x2, . . . , xn 0,

3 функции проектирования Imn x1, x2, . . . , xn xm

с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и минимизации.

29

Как и при определении примитивной рекурсивности, можно выразить определение частично рекурсивной функции в виде трех правил.

1 Простейшие функции

s x x 1, on x1, x2, . . . , xn 0, Imn x1, x2, . . . , xn xm

частично рекурсивны.

2 Если функция f получена из частично рекурсивных функций с помощью операторов суперпозиции, примитивной рекурсии или минимизации, то функция f частично рекурсивна.

3 То, что функция f частично рекурсивна, устанавливается несколькими применениями правил 1 и 2 .

Всякой частично рекурсивной функции можно приписать n — наименьший номер шага, на котором она может быть получена.

В отличие от определения примитивной рекурсивности, где имелись два оператора, теперь имеются три оператора для получения частично рекурсивных функций. Ясно, что всякая примитивно рекурсивная функция является частично рекурсивной функцией. Оператор минимизации может вырабатывать не всюду определенные функции, а примитивно рекурсивные функции всюду определены. Поэтому существуют частично рекурсивные функции, которые не являются примитивно рекурсивными функциями.

Ранее мы сформулировали понятие вычислимой рекурсивной функции и отметили, что это нестрогое, интуитивное понятие. Однако для приведенного выше понятия частично рекурсивной функции справедливо следующее утверждение.

Понятие частично рекурсивной функции является строгим математическим понятием.

ОПРЕДЕЛЕНИЕ 4.3. Всюду определенная, рекурсивная функция называется общерекурсивной функцией.

Словосочетание «функция f частично рекурсивна» будем заменять на более краткое словосочетание «f рекурсивна».

30