Подзоров С.Ю. Теория алгоритмов. Полный конспект лекций по курсу

Подождите немного. Документ загружается.

Более того, в настоящий момент не представляется возможным приду-

мать хоть какой-нибудь алгоритм, инструкции которого нельзя было бы

промоделировать в виде команд машины Тьюринга. В связи с этим все

математики в настоящее время принимают

Тезис Тьюринга: Всякая вычислимая (согласно определению 9) ча-

стичная функция из Σ

∗

в Σ

∗

вычислима на машине Тьюринга.

Тезис Тьюринга нельзя доказать, потому что определение 9 не яв-

ляется математическим определением. Однако им можно пользоваться:

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

∗

в Σ

∗

, данное на обычном

языке, можно, пользуясь этим тезисом, утвер-

ждать, что существует программа для машины Тьюринга, реализующая

этот алгоритм, не выписывая саму программу. Со временем и мы станем

так поступать. А пока продолжим изложение на формальном уровне.

Переходим к рассмотрению частичных функций на натуральных чис-

лах со значениями в N. Мы будем рассматривать частичные функции от

нескольких аргументов. Количество аргументов функции мы называем

ее местностью или арностью. Для каждого натурального числа k k-

местная (или k-арная) функция — это функция от k аргументов. Ясно,

что такое k-местная частичная функция для k > 0; для k = 0 0 -мест-

ная частичная функция из N в N — это просто константа, равная либо

некоторому натуральному числу, либо неопределенному значению

Пусть k, n ∈ N и имеется одна n-местная частичная функция g(x

, . . . ,

) и n k-местных частичных функций f

, . . . , x

), . . . , f

, . . . , x

Например, русском.

Можно представлять себе ситуацию следующим образом. Часто встречаются слу-

чаи, когда значение функции от нескольких аргументов реально зависит от меньшего

числа аргументов. Например, есть функция от двух аргументов f(x, y) = x + y; зна-

чение f (x, y) зависит как от x, так и от y. Есть другая функция от двух аргументов:

g(x, y) = x + (y − y). Значение g(x, y) зависит только от того, чему равен x. Фор-

мально g — это 2-местная функция, но ее можно рассматривать и как одноместную

функцию g

(x) = x. Мы в нашем курсе считаем, что функции g и g

— разные, хотя

бы потому что это функции разной местности, однако нельзя отрицать, что функ-

ция g

в некотором смысле соответствует функции g. Теперь рассмотрим функцию

h(x, y) = 2, равную константе 2 при всех значениях x и y. В том же смысле, в ка-

ком функции g соответствовала функция g

, функции h соответствуют две 1-местные

функции h

(x) = 2 и h

(y) = 2, а также 0-местная функция, равная константе 2. Если

мы рассмотрим 2-местную частичную функцию h

(x, y), которая не определена при

всех значениях x и y (δh = ∅), то ей соответствует 0-местная функция с неопреде-

ленным значением.

Мы говорим, что k-местная частичная функция h является суперпози-

цией функций g, f

, . . . , f

, если h(x

, . . . , x

) = g(f

, . . . , x

), . . . , f

. . . , x

)). Для набора натуральных чисел m

, . . . , m

значение h(m

, . . . ,

) определено тогда и только тогда, когда во-первых определены чис-

ла l

= f

, . . . , m

), . . . , l

= f

, . . . , m

), а во-вторых, определено

g(l

, . . . , l

). Заметим, что если g, f

, . . . , f

— всюду определенные функ-

ции, то h также всюду определена.

Пусть теперь k ∈ N и есть одна k-местная частичная функция g(x

, . . . ,

) и одна (k + 2)-местная частичная функция h(z, y, x

, . . . , x

). Мы го-

ворим, что (k + 1) -местная частичная функция f (t, x

, . . . , x

) получа-

ется из функций g и h по схеме примитивной рекурсии, если для всех

t, x

, . . . , x

∈ N выполнены следующие равенства:

f(0, x

, . . . , x

) = g(x

, . . . , x

)

f(t + 1, x

, . . . , x

) = h(f(t, x

, . . . , x

), t, x

, . . . , x

)

Ясно, что эти два равенства однозначно определяют значение функции

f на всех аргументах. Область определения f следует из способа ее за-

дания. Пусть, например, m

, . . . , m

∈ N. Тогда f(0, m

, . . . , m

) опре-

делено тогда и только тогда, когда определено g(m

, . . . , m

). Значе-

ние f(1, m

, . . . , m

) определено тогда и только тогда, когда определены

f(0, m

, . . . , m

) и h(f(0, m

, . . . , m

), 0, m

, . . . , m

). Значение f(2, m

, . . . ,

) определено тогда и только тогда, когда определены f(1, m

, . . . , m

)

и h(f(1, m

, . . . , m

), 1, m

, . . . , m

). И так далее. Получаем, что при фик-

сированных m

, . . . , m

множество чисел t, таких что функция f опреде-

лена на наборе t, m

, . . . , m

, равно либо всему натуральному ряду, либо

конечному множеству {1, . . . , n} для некоторого n > 0. Отметим еще, что

если g и h всюду определены, то f также всюду определена.

Мы будем называть базисными (или базовыми) следующие функции:

1. 0-местную функцию, равную константе 0;

2. 1-местную функцию s(x) = x + 1;

3. для каждого n > 1 и каждого 1 6 k 6 n n-местную функцию

, . . . , x

) = x

Определение 14 Функция f называется примитивно рекурсивной, ес-

ли существует конечная последовательность функций f

, . . . , f

, такая

что f

= f и для каждого 1 6 i 6 n функция f

либо базисная, либо по-

лучается из предыдущих членов последовательности суперпозицией или

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

Другими словами, примитивно рекурсивные функции — это функ-

ции, которые можно получить из базисных при помощи конечного числа

суперпозиций и примитивных рекурсий. Так как базисные функции всю-

ду определены, то каждая примитивно рекурсивная функция является

всюду определенной.

Предложение 1 Следующие функции являются примитивно рекурсив-

ными:

1. 0-местная функция, равная константе k для произвольного k ∈ N;

2. 1-местная функция o(x), равная нулю для всех x;

3. 1-местная функция, равная константе k при всех x для произволь-

ного k ∈ N;

4. 2-местная функция x + y;

5. 2-местная функция x · y;

6. 1-местная функция x

1, равная 0 при x = 0 и x − 1 при x > 0;

7. 2-местная функция x

y, равная 0 при x < y и x − y при x > y.

Доказательство. (1) Для k ∈ N 0-местная функция, равная k, по-

лучается при при помощи k суперпозиций из базисных функций s и 0

(k = ss . . . s(0), символ s встречается в записи k раз).

(2) и (3) Ясно, что (2) — это частный случай (3). Пусть для k ∈ N

(x) = k — одноместная функция, равная константе k. Тогда f

полу-

чается по схеме примитивной рекурсии из 0-местной функции k и двух-

местной функции I

следующим образом:

(0) = k

(t + 1) = I

(t), t)

(4) Эта функция получается по схеме примитивной рекурсии из од-

номестной функции I

(x) и трехместной функции s(I

(z, y, x)):

x + 0 = I

(x)

x + (t + 1) = s(I

(x + t, t, x))

(5) Эта функция получается по схеме примитивной рекурсии из од-

номестной функции o(x) и трехместной функции I

(z, y, x) + I

(z, y, x):

x · 0 = o(x)

x · (t + 1) = I

(x · t, t, x) + I

(x · t, t, x)

(6) Эта функция получается по схеме примитивной рекурсии из 0-

местной функции 0 и 2-местной функции I

(z, y):

1 = 0

(t + 1)

1 = I

t, t)

(7) Эта функция получается по схеме примитивной рекурсии из од-

номестной функции I

(x) и трехместной функции I

(z, y, x)

0 = I

(x)

(t + 1) = I

t, t, x)

1 ¤

Сделаем одно замечание по поводу доказательства. Рассмотрим, на-

пример, пункт 5. В этом пункте приведена схема примитивной рекурсии,

которая задает двухместную функцию f(x, y) = x · y. Согласно опре-

делению примитивной рекурсии, в этой схеме должны участвовать две

функции g и h, такие что число аргументов у функции g на единицу

меньше, чем у f, а у h, наоборот, на единицу больше. Соответственно,

в доказательстве g(x) = I

(x) и h(z, y, x) = I

(z, y, x) + I

(z, y, x). Функ-

ция g базисная. Функция h получается суперпозицией из двухместной

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

в предыдущем пункте, и двух трехместных базисных функций I

и I

Таким образом, все формальности соблюдены. Можно было бы напи-

сать просто h(z, y, x) = z + x и это выглядело бы более понятно, однако

такая запись формально является некорректной. Дело в том, что если

мы хотим получить трехместную функцию при помощи суперпозиции

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

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

быть функцией от тех же самых аргументов, что и функция, которую

мы хотим получить. А в записи z+x вместе с двухместной функцией сло-

жения участвуют две одноместные функции f

(z) = z и f

(x) = x, при-

чем от разных аргументов, и получается запись, формально не имеющая

никакого смысла. Тем не менее, запись z + x выглядит более понятной

и лучше отражает смысл функции h, а восстановить по ней формально

корректную запись I

(z, y, x) + I

(z, y, x) не составляет труда. В связи

с этим мы больше не будем загромождать изложение обилием лишних

формальностей и если нам потребуется, например, записать схему при-

митивной рекурсии из пункта 5, мы вместо строгой с формальной точки

зрения записи, приведенной в доказательстве предложения 1, будем пи-

сать просто

x · 0 = 0

x · (t + 1) = x · t + x,

считая, что восстановить по этой записи правильную запись не состав-

ляет труда.

Предложение 2 Пусть f(y, x

, . . . , x

) — примитивно рекурсивная функ-

ция. Тогда следующие функции являются примитивно рекурсивными:

1. Sum

(y, x

, . . . , x

) =

i=0

f(i, x

, . . . , x

);

2. Prod

(y, x

, . . . , x

) =

i=0

f(i, x

, . . . , x

Доказательство. (1) Функция Sum

задается следующей схемой при-

митивной рекурсии:

Sum

(0, x

, . . . , x

) = f(0, x

, . . . , x

)

Sum

(t + 1, x

, . . . , x

) = Sum

(t, x

, . . . , x

) + f(s(t), x

, . . . , x

)

(2) Функция Prod

задается схемой примитивной рекурсии:

Prod

(0, x

, . . . , x

) = f(0, x

, . . . , x

)

Prod

(t + 1, x

, . . . , x

) = Prod

(t, x

, . . . , x

) · f(s(t), x

, . . . , x

) ¤

Для k ∈ N под k-местным предикатом мы понимаем функцию из

в двухэлементное множество {истина, ложь}. Мы говорим, что k-

местный предикат P (x

, . . . , x

) истинен на наборе m

, . . . , m

∈ N, если

значение P (m

, . . . , m

) равно истине. В противном случае мы говорим,

что предикат ложен на этом наборе. В качестве примера приведем двух-

местный предикат P (x, y) =”x 6 y”. Этот предикат истинен на наборе 2, 3

(то есть P (2, 3) истинно) и ложен на наборе 5, 4 (P (5, 4) ложно). Вообще,

для m, n ∈ N P (m, n) истинно тогда и только тогда, когда m 6 n.

Под конъюнкцией предикатов P (x

, . . . , x

) и Q(x

, . . . , x

) (обознача-

ется P (x

, . . . , x

) & Q(x

, . . . , x

)) мы понимаем предикат, который ис-

тинен на наборе x

, . . . , x

тогда и только тогда, когда на этом набо-

ре истинны сразу оба предиката: P и Q. Под дизъюнкцией предикатов

P (x

, . . . , x

) и Q(x

, . . . , x

) (обозначается P (x

, . . . , x

) ∨ Q(x

, . . . , x

))

понимается предикат, который истинен на наборе x

, . . . , x

тогда и толь-

ко тогда, когда на этом наборе истиннен хотя бы один из этих двух преди-

катов. Отрицанием предиката P (x

, . . . , x

) (обозначается ¬P (x

, . . . , x

))

называется предикат, который истинен на наборе x

, . . . , x

тогда и толь-

ко тогда, когда предикат P ложен на этом наборе. Если P(x

, . . . , x

) —

k-местный предикат, то под его характеристической функцией (обозна-

чается χ

) понимается всюду определенная функция от k аргументов,

такая что

, . . . , x

) =

(

1, если P (x

, . . . , x

) истинно

0, если P (x

, . . . , x

) ложно,

Определение 15 Предикат P (x

, . . . , x

) называется примитивно ре-

курсивным, если его характеристическая функция является примитивно

рекурсивной.

Предложение 3 Следующие функции и предикаты являются прими-

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

1. Одноместная функция

sg(x) =

(

1, если x = 0

0, если x > 0;

2. Одноместная функция

sg(x) =

(

0, если x = 0

1, если x > 0;

3. Двухместный предикат ”x 6 y”;

4. Двухместный предикат ”x = y”.

Доказательство. (1) sg(x) = 1

(2) sg(x) = 1

sg(x).

(3) Для P (x, y) =”x 6 y” χ

(x, y) = sg(s(y)

x).

(4) Для P (x, y) =”x = y” χ

(x, y) = sg((y

x) + (x

y)). ¤

Предложение 4 Справедливы следующие утверждения:

1. конъюнкция и дизъюнкция примитивно рекурсивных предикатов

являются примитивно рекурсивными предикатами;

2. отрицание примитивно рекурсивного предиката есть примитивно

рекурсивный предикат;

3. если P (x

, . . . , x

) — k-местный примитивно рекурсивный преди-

кат и f

, . . . , x

), . . . , f

, . . . , x

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

функции, то n-местный предикат P (f

, . . . , x

), . . . , f

, . . . , x

))

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

Доказательство. (1) χ

P &Q

, . . . , x

) = χ

, . . . , x

)·χ

, . . . , x

)

и χ

P ∨Q

, . . . , x

) = sg(χ

, . . . , x

) + χ

, . . . , x

)).

(2) χ

¬P

, . . . , x

) = sg(χ

, . . . , x

)).

(3) Пусть Q(x

, . . . , x

) = P (f

, . . . , x

), . . . , f

, . . . , x

)). Тогда

, . . . , x

) = χ

, . . . , x

), . . . , f

, . . . , x

)). ¤

Следствие 3 Двухместные предикаты ”x < y” и ”x 6= y” являются при-

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

Доказательство. ”x 6= y” = ¬”x = y” и ”x < y”=”x 6 y” & ”x 6= y”. ¤

Пусть P (y, x

, . . . , x

) — (k + 1)-местный предикат. Определим функ-

цию от k + 1 аргумента f(y, x

, . . . , x

) следующим образом:

f(y, x

, . . . , x

) =











, если i

6 y, P (i

, x

, . . . , x

) истинно и для

всех i < i

P (i, x

, . . . , x

) ложно

y + 1, если не существует i 6 y, такого что

P (i, x

, . . . , x

) истинно.

Другими словами, значение f(y, x

, . . . , x

) равно минимальному числу

i 6 y, для которого предикат P (i, x

, . . . , x

) истинен или числу y + 1,

если такого i не существует. Определенную таким образом функцию f мы

будем обозначать (µi 6 y)P (i, x

, . . . , x

) и говорить, что она получается

из предиката P при помощи ограниченной минимизации.

Предложение 5 Если P (y, x

, . . . , x

) — примитивно рекурсивный пре-

дикат, то функция (µi 6 y)P (i, x

, . . . , x

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

Доказательство. Введем вспомогательную функцию g(j, x

, . . . , x

) =

i=0

¬P

(i, x

, . . . , x

). По предложениям 2 и 4 она примитивно рекурсив-

на. Остается заметить, что (µi 6 y)P (i, x

, . . . , x

) =

j=0

g(j, x

, . . . , x

Предложение 6 Следующие функции и предикаты являются прими-

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

1. одноместная функция x!;

2. двухместная функция x

(считаем, что 0

= 1);

3. двухместная функция

div(x, y) =

(

[x/y], если y > 0

x, если y = 0;

4. двухместная функция

rest(x, y) =

(

остаток от деления x на y, если y > 0

x, если y = 0;

5. двухместная функция

log(x, y) =











наибольшему k, такому

что y делится на x

, если y > 0 и x > 1

y, если x = 1

0, если x = 0 или y = 0;

6. одноместный предикат P (x), истинный тогда и только тогда, когда

x — простое число;

7. одноместная функция p, такая что для i ∈ N p(i) — i-ое простое

число (p(0) = 2, p(1) = 3, p(2) = 5 и т. д.).

Доказательство. (1) Функция x! задается следующей схемой прими-

тивной рекурсии:

0! = 1

(t + 1)! = t! · s(t)

(2) Функция x

задается следующей схемой примитивной рекурсии:

= 1

t+1

= x

· x

(3) div(x, y) = (µi 6 x)(x < i · y)

(4) rest(x, y) = x

y ·div(x, y).

(5) log(x, y) = (µi 6 y)(rest(y, x

) 6= 0)

(6) P (x) = ”(µi 6 x)(rest(x, i + 2) = 0) + 2 = x”.

(7) Функция p(x) задается следующей схемой примитивной рекурсии:

p(0) = 2

p(t + 1) = (µi 6 p(t)! + 1)(”i > p(t)” & P (i)),

ибо чему бы ни было равно x, в промежутке [x + 1, x! + 1] обязательно

найдется хотя бы одно простое число. ¤

Для дальнейших рассмотрений нам понадобится следующая двух-

местная функция:

c(x, y) =

(x + y)

+ 3x + y

Легко заметить, что число, стоящее в числителе дроби, будет четным для

любых натуральных x и y, так что функция c принимает только целые

значения.

Предложение 7 Справедливы следующие утверждения:

1. функция c(x, y) примитивно рекурсивна;

2. функция c взаимно однозначно отображает N

на N;

3. если x

6 x

и y

6 y

, то c(x

, y

) 6 c(x

, y

);

4. для любых x, y ∈ N x 6 c(x, y) и y 6 c(x, y).

Доказательство. Пункты 1, 3 и 4 очевидны. Докажем пункт 2.

Сначала покажем, что если x

6= x

или y

6= y

, то c(x

, y

) 6= c(x

, y

Пусть x

6= x

или y

6= y

. Возможны два случая.

1. x

+ y

= x

+ y

. Тогда x

6= x

. Имеем c(x

, y

) − c(x

, y

) =

− x

6= 0.

2. x

+ y

6= x

+ y

. Без ограничения общности можно считать, что

< x

. Заметим, что для любых x, y ∈ N (x+y)(x+y+1) 6

2c(x, y) < (x + y + 1)(x + y + 2). Имеем 2c(x

, y

) < (x

+ y

+ 1)(x

+ 2) 6 (x

+ y

)(x

+ y

+ 1) 6 2c(x

, y

Осталось доказать, что для любого z ∈ N существуют натуральные

числа x и y, такие что z = c(x, y). Установим справедливость этого утвер-

ждения индукцией по z. Для z = 0 имеем 0 = c(0, 0). Пусть теперь для

некоторых x и y z = c(x, y). Тогда если y 6= 0, то z + 1 = c(x + 1, y −1), а

если y = 0, то z + 1 = c(0, x + 1). ¤

В связи с пунктом 2 предложения 7 для любого натурального числа

z существуют единственные x и y, такие что z = c(x, y). Обозначим x,

который однозначно находится по z, через l(z), а y — через r(z).

Предложение 8 Одноместные функции l(z) и r(z) примитивно рекур-

сивны.

Доказательство. Введем вспомогательную двухместную функцию

α(z, y) = (µi 6 z)(z 6 c(i, y)). Тогда, по пунктам 3 и 4 предложения 7,

имеем r(z) = (µi 6 z)(c(α(z, i), i) = z) и l(z) = (µi 6 z)(c(i, r(z)) = z).

Действительно, при каждом фиксированном y c(0, y) < c(1, y) < . . . и,

следовательно, почти для всех i z 6 c(i, y). Значение α(z, y) равно ми-

нимальному такому i, поскольку оно не превосходит z Для этого i нера-

венство z 6 c(i, y) превратится в равенство в том и только в том случае,

если y = r(z). Таким образом, чтобы вычислить r(z), достаточно найти

(очевидно, единственный) y, для которого z = c(α(z, y), y). ¤

Настала пора отойти на время от формальных рассмотрений и сно-

ва поговорить об основных понятиях нашего курса: о конструктивных

пространствах и вычислимых функциях. В определении 4 мы обозна-

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