A08DPPMAT_UPS2006D00

Лекция 2. Конструктивные объекты. Числовые функции и алгоритмы их вычисления

Конструктивные объекты. В современной математике, в особенности в теории алгоритмов, нужно четко представлять различие между «конструктивными» и «неконструктивными» подходами в рассмотрении объектов и законов логики. Для того чтобы правильного понимать понятие алгоритма, нужно ответить на следующий вопрос.

Какие объекты поступают на вход алгоритма, какие объекты возникают в процессе вычислений и на выходе алгоритма?

Ответ следующий — конструктивные объекты. Слова «вычислительная процедура» в определении алгоритма нужно понимать в широком смысле, а не только как числовые вычисления. Исходными и промежуточными данными, а также и результатом алгоритмического процесса являются конструктивные объекты. Понятие конструктивного объекта является первичным, неопределяемым понятием теории алгоритмов, которое разъясняется далее на ряде примеров.

Простейшим примером конструктивных объектов являются слова в некотором алфавите. Пусть

A a, b, c, . . .

конечное множество, которое назовем алфавитом. Элементы множества A будем называть буквами или символами. Можно рассматривать и счетные алфавиты. В таком случае буквами являются также знаки вида

a1, b , c и т.п.

Словом в алфавите A называется конечная последовательность

u a1a2 . . . an

(2.1)

букв алфавита A . Натуральное число n 0 называется длиной слова u. В теории алгоритмов число 0 удобно считать натуральным числом. Поэтому множество натуральных чисел имеет вид

N 0, 1, 2, . . . .

Слово длины 0 называется пустым словом. Оно не имеет ни одной буквы и обозначается через Λ.

Покажем, что сложение натуральных чисел можно рассматривать как алгоритм переработки слов. Пусть, например, на входе алгоритма имеется слово P 12 24 длины 5. Тогда на выходе получим слово Q 36.

11

Оба слова P и Q являются словами в алфавите A 0, 1, . . . , 9, , состоящем из 11 символов — цифр и знака +. Поэтому алгоритм сложения натуральных чисел перерабатывает конструктивные объекты — слова в алфавите A .

Можно указать другие конструктивные объекты: натуральные числа, записанные в какой-либо системе счисления; слова в естественном языке; формулы в алгебре высказываний. В школьном курсе алгебры рассматриваются буквенные выражения, в высшей алгебре — матрицы, а в дискретной математике — графы, в информатике — программы на каком-либо языке программирования. В случае нелинейной записи, на-

пример, записи матрицы в виде
10	12	5
A 3	24	7
6	5	3Æ

легко перейти к линейной записи матрицы в виде слова

A10, 12, 5 , 3, 24, 7 , 6, 5, 3 .

Это запись матрицы A в компьютерной системе GAP, предназначенной для вычислений в дискретной математике.

Конструктивный объект A можно представить сконструированным из подобъектов A1, A2, . . .. Эти подобъекты также собраны из меньших частей B1, B2, . . . и т.д. Наконец, мы доходим до частей, не составленных из меньших частей. Это символы, распознаваемые в один прием. Они образуют алфавит, в котором рассматриваемые объекты можно выразить в виде слов с помощью линейной записи. Именно так мы поступили с матрицей A, перейдя к линейной записи матрицы в виде слова A 10, 12, 5 , 3, 24, 7 , 6, 5, 3 . При этом частями матрицы были строки. Они образованы из своих частей — элементов строк. Элементы строк составлены из символов алфавита 0, 1, . . . , 9, .

Итак, мы установили следующее утверждение.

Конструктивные объекты при подходящей записи могут быть представлены словами в некотором конечном алфавите.

Оперируя с конструктивным объектом A по заданным инструкциям алгоритма, мы делаем определенные преобразования этого объекта. Данные преобразования учитывают расчлененность, дискретное построение объекта A из своих частей и состоят в локальной замене некоторых ча-

12

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

Следующие объекты не являются конструктивными объектами. Мы не можем представить их в виде слов в некотором конечном алфавите.

1)Действительное число α, являющееся бесконечной десятичной дробью.

2)Произвольная функция f x из N в N.

Счетные множества. Напомним некоторые сведения о счетных множествах.

Множество A называется равномощным множеству B, если существует биективное (взаимно однозначное) отображение множества A во множество B. Если A равномощно B, то B равномощно A.

Множество A называется счетным множеством, если оно равномощно множеству натуральных чисел N. В этом случае существует биекция f : N A и элемент a с условием f n a можно обозначить через

an. Получим запись A a0, a1, a2, . . . , где ai aj при i j. Обратно, из такой записи следует счетность множества A. Получили следующее

утверждение.

ПРЕДЛОЖЕНИЕ 2.1. Множество A счетно, тогда и только тогда, когда его элементы можно представить в виде бесконечной последовательности без повторений

A a0, a1, a2, . . . , где ai aj при i j.

(2.2)

Пример. Множество целых чисел Z счетно, так как целые числа можно расположить в виде последовательности 0, 1, 1, 2, 2, 3, 3, . . . .

Отметим следующие известные свойства счетных множеств.

ПРЕДЛОЖЕНИЕ 2.2 . 1 Подмножество счетного множества конечно или счетно.

2 Объединение конечного или счетного числа конечных или счетных множеств конечно или счетно.

3 Множество действительных чисел не является счетным множеством.

4 Множество M , состоящее из всех строк x1, x2, . . . , xn произвольной длины n 0, где xi N, является счетным множеством.

5 Пусть A — конечный алфавит и X — множество всех слов в алфавите A. Тогда множество X является счетным множеством.

13

Пусть M — бесконечное множество конструктивных объектов, являющихся множеством входных объектов некоторого алгоритма. Множество M можно рассматривать как множество слов в некотором алфавите. По пункту 5) предложения 2.2 множество M является счетным множеством.

Алгоритмы и функции. Вариант строгого определения алгоритма, предложенный Черчем и Клини, рассматривает алгоритмический процесс как процесс вычисления значений некоторой функции f , определенной на множестве N. Рассмотрим обоснование такой позиции.

Пусть имеется некоторый алгоритм A. На его вход поступает объект P — набор данных u1, u2, . . . , un. Каждый конструктивный объект ui есть слово в некотором алфавите A . Слова в алфавите A образуют счетное множество и занумерованы натуральными числами. Поэтому каждый конструктивный объект u имеет номер x N . Такая операция присвоения номеров называется кодированием объектов. Число x, присвоенное объекту, называется его кодовым номером. Отметим, что определение номера по объекту и восстановление объекта по номеру должно осуществляться с помощью некоторых алгоритмов. Подробно нумерации рассматриваются в лекции 8.

Вместо конструктивных объектов u1, u2, . . . , un во всевозможных вычислениях можно рассматривать их кодовые номера x1, x2, . . . , xn. Предположим на вход алгоритма A поступила строка конструктивных объектов u1, u2, . . . , un, а на выходе алгоритма получен объект v с номером y. Переходя к кодовым номерам, можно считать, что на входе была строкаx1, x2, . . . , xn из n натуральных чисел, а на выходе число y N .

x1, x2, . . . , xn Инструкции алгоритма y

Инструкции алгоритма рассматриваем как «правило по которому строке x1, x2, . . . , xn сопоставляем элемент y N ». Если учесть обычное определение функции f x1, x2, . . . , xn на множестве N как «правило, которое каждому набору аргументов x1, x2, . . . , xn ставит в соответствие значение функции», то получаем следующую возможную точку зрения на понятие алгоритма.

Алгоритм A вычисляет некоторую n-арную функцию f x1, x2, . . . , xn , определенную на множестве N.

14

Слова «определенную на множестве N» означают, что вместо переменных подставляются натуральные числа. Из вышесказанного понятно, почему в теории алгоритмов функции, определенные на множестве натуральных чисел, являются одним из основных предметов обсуждения.

Частичные функции. При наших рассмотрениях нужно учесть следующий факт. Когда имеется какой-либо объект P на входе алгоритма, то совсем необязательно, что он переработается в некоторый объект Q на выходе алгоритма. Следовательно, функция f , которую вычисляет алгоритм A такова, что ее значения могут быть определены не для всех наборов аргументов. В связи с этим возникает понятие частичной функции. Пусть n N.

ОПРЕДЕЛЕНИЕ 2.1 . Частичной n-арной функцией f , заданной на множестве натуральных чисел, называется правило, которое некоторым наборам x1, x2, . . . , xn натуральных чисел ставит в соответствие однозначно определенное число f x1, x2, . . . , xn N.

Итак, значение функции f x1, x2, . . . , xn может не существовать. Множество X, состоящее из всех наборов x1, x2, . . . , xn , для которых существует значение функции, называется областью определения функции f и обозначается через Dom(f ). Множество всех значений функции f называется областью значений функции f и обозначается через Ran(f ).

Множество всех строк x1, x2, . . . , xn , где xi N для i 1, 2, , . . . , n, обозначается через Nn и называется n -ной степенью множества N. По-

этому Dom f Nn и Ran(f ) N. При этом

Dom f	x1, x2, . . . , xn	f x1, x2, . . . , xn существует ,	(2.3)
Ran f	f x1, x2, . . . , xn	x1, x2, . . . , xn N .	(2.4)

Тем самым n-арная частичная функция f — это отображение некоторого подмножества X Dom f из Nn во множество N . Отсюда следует

ЗАМЕЧАНИЕ 2.1 . Пусть f — n-арная частичная функция с условием Dom f . Тогда число n определено однозначно.

Наряду со словами f — n-арная функция, будем говорить также, что f — функция от n переменных (от n аргументов).

15

Назовем функцию f всюду определенной, если ее значение определено при любом наборе аргументов. Поэтому частичная функция f x1, x2, . . . , xn всюду определена тогда и только тогда, когда Dom(f)=Nn.

При n 0 мы будем рассматривать всюду определенную нуль-арную функцию f , не имеющую аргументов. Тогда значения функции f не могут изменяться и равны некоторому числу a. В этом случае функция f (функция выделения числа a) отождествляется с числом a.

Приведенные выше определения дословно переносятся на случай, когда вместо множества N выступает произвольное множество A. Если задана функция f , сопоставляющая элементам множества A элементы множества B, то применяем краткую запись: функция f : A B. Если при этом Dom f A, то говорим также, что f — отображение множества A во множество B.

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

ОПРЕДЕЛЕНИЕ 2.2. Функция f x1, x2, . . . , xn называется вычислимой, если существует алгоритм A, вычисляющий функцию f .

Слова «алгоритм A вычисляет функцию f » означают следующее.

1) Если на вход алгоритма A поступает набор аргументовx1, x2, . . . , xn из области определения функции f , то алгоритм останав-

ливается и выдает результат f x1, x2, . . . , xn .

2) Если на вход алгоритма A поступает набор аргументов вне области определения функции f , то алгоритм работает бесконечно или останавливается без выдачи результата.

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

Понятие вычислимой функции является интуитивным понятием, не имеющим строгого определения.

В следующей лекции интуитивное понятие вычислимой функции будет сопоставлено со строгим математическим понятием частично рекурсивной функции.

16

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

ЗАДАЧА 1. Пусть K — множество всех многочленов f x с целыми коэффициентами.

1 Можно ли считать, что K — множество конструктивных объектов?

2 Если да, то какой алфавит A используется для записи элементов из K?

3 Как перейти к линейной записи в алфавите A произвольного многочлена f x axn bxn 1 c K? В каком языке программирования применяется данная запись?

	ЗАДАЧА 2. Пусть X — множество всех слов в алфавите
A	a, b, c . Занумеровать элементы из множества X в лекси-

кографическом порядке так, чтобы вначале располагалось пустое слово с номером 0, затем слова длины 1, длины 2 и т.д. Какой номер получит слово P aac при данной нумерации?

ЗАДАЧА 3. Построить биективное отображение множества A во множество B, где

1 A N,		B x Z x 0 ;
2 A	N,	B Z;
3 A	N,	B — множество нечетных натуральных чисел;

4 A — множество нечетных натуральных чисел, B — множество четных целых чисел, меньших 5;

	5 A	R,			B		R x R x 0 ;
	6 A		π	,		π	, B R .
			2		2

ЗАДАЧА 4. Построить биективное отображение множества строк a1, a2, . . . , an , где каждая компонента равна 0 или 1, во множество всех подмножеств произвольного множества из n элементов.

ЗАДАЧА 5. Пусть A – конечный или счетный алфавит. Доказать, что множество всех слов в алфавите A счетно.

17

ЗАДАЧА 6. Доказать, что подмножество счетного множества конечно или счетно.

ЗАДАЧА 7. Доказать, что объединение конечного или счетного числа конечных или счетных множеств конечно или счетно.

ЗАДАЧА 8. Доказать, что множество рациональных чисел является счетным множеством.

ЗАДАЧА 9. Доказать, что множество действительных чисел из интервала a, b не является счетным множеством.

ЗАДАЧА 10. Пусть f x, y — функция, определенная на множестве N со значениями в N. Описать множества Dom f и Ran f , где

	1 f x, y	x y,
	2 f x, y	x		y,
	3 f x, y	xy,
	4 f x, y		x	,
			y
	5 f x, y	xy при этом 00 1 ,
	6 f x, y		x	,
		2
				1
	7 f x, y		x		,
				2
	8 f x, y
			x y .

Какие из данных функций являются всюду определенными?

18

Лекция 3. Примитивно рекурсивные функции

В предыдущей лекции отмечено, что алгоритмический процесс можно рассматривать как процесс вычисления значений некоторой функции f . Такую функцию f мы назвали вычислимой функцией. Интуитивное понятие вычислимой функции мы заменим на точное понятие частично рекурсивной функции. В результате получим строгое определение алгоритма.

Исходные функции. Рассмотрим некоторый набор простейших функций, вычислимость которых очевидна.

Функция следования. Рассмотрим функцию s x , заданную правилом

s x x 1 для всех x N.

(3.1)

Эта функция очевидно вычислима, т.к. алгоритм ее вычисления состоит из простейшего действия «добавления к x палочкам еще одной палочки». Функция s x называется функцией следования.

Нулевая функция. Пусть n 0. Рассмотрим n-арную функцию on x1, x2, . . . , xn , заданную правилом

on x1, x2, . . . , xn 0 для всех x1, x2, . . . , xn N.

(3.2)

Данная функция называется нулевой функцией. Нулевая функция, как и функция следования, очевидно вычислима. Нулевую функцию при n 1 обозначаем через o x . Поэтому

o x 0 для всех x N.

Нулевая функция при n 0 обозначается через o0 и отождествляется с числом 0.

Функция проектирования. Пусть n 1 и 1 m n. Зададим

функцию проектирования Imn x1, x2, . . . , xn правилом
In	x	, x	, . . . , x	n		x	m	.	(3.3)
m	1	2

Данная функция строке аргументов x1, x2, . . . , xn сопоставляет ее компоненту xm с номером m. Вычислимость функции проектирования обеспечивается нашей способностью найти в строке x1, x2, . . . , xn место с номером m и указать число на этом месте.

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

19

ПРЕДЛОЖЕНИЕ 3.1. Следующие простейшие функции вычислимы.

Функция следования s x x 1. Нулевая функция on x1, x2, . . . , xn 0.

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

Итак, у нас имеется исходный набор простейших (базисных) вычислимых функций. Мы будем пополнять этот набор вычислимых функций. Для этого рассмотрим способы построения из уже имеющихся вычислимых функций новых вычислимых функций.

Оператор суперпозиции S. Рассмотрим действие, которое назовем оператором суперпозиции (регулярной суперпозиции). С помощью этого действия из некоторых функций h, g1, g2, . . . , gm создается новая функ-

ция f .
Пусть дана функция h от	m переменных	и заданы m функций
g1, g2, . . . , gm от n переменных.	При этом m, n	0. Новую функцию

f x1, x2, . . . , xn определим по следующему правилу:

f x1, x2, . . . , xn

h g1 x1, x2, . . . , xn , g2 x1, x2, . . . , xn , . . . , gm x1, x2, . . . , xn . (3.4)

Функция f является частичной функцией от n переменных. Ее значение f x1, x2, . . . , xn определено тогда и только тогда, когда определены все выражения в правой части из (3.4). Если функции h и g1, g2, . . . , gm вычислимы, то и функция f вычислима. Алгоритм ее вычисление описывается правой частью в (3.4). В случае существования значения функции f , мы за конечное число шагов получим число f x1, x2, . . . , xn действиями, соответствующими интуитивному представлению об алгоритме.

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

f S h, g1, g2, . . . , gm .

(3.5)

Пусть m 1, n 1 в равенстве (3.4) и функция f x получена оператором суперпозиции из функций h x и g x . Тогда имеем запись

f x h g x для всех x N.

(3.6)

20