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

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

пространства в другое. В определениях 9 и 10 мы задали ограничение

этого понятия для частного случая функций, отображающих Σ

∗

в Σ

∗

. Мы

также увидели, что общий случай сводится к частному и что для того,

чтобы изучать вычислимые функции, отбражающие одно конструктив-

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

из Σ

∗

в Σ

∗

. Однако редукция к функциям из Σ

∗

в Σ

∗

— это не един-

ственный способ изучать функции из конструктивного пространства K

в конструктивное пространство K

. Для некоторых K

и K

возможны и

другие подходы.

Остановимся на случае, когда K

= N, а K

равно одному из следу-

ющих множеств: N

, N

, . . .. Для K

= N

функция из K

в K

— это

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

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

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

значения функции.

Речь опять зашла об описаниях. Существует множество традицион-

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

ральных чисел в виде слов конечного алфавита. Например, можно за-

фиксировать алфавит {0, . . . , 9,

} и задавать последовательность

, . . . , n

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

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

ления взять, например, двоичную или любую другую, а вместо запятой

использовать какой-либо иной разделитель. Все это малосущественно,

поскольку любой ”естественный” способ задания конечных последова-

тельностей натуральных чисел алгоритмически сводится к описанному

выше

. Примем один из способов задания натуральных чисел и после-

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

При выборе любого ”естественного” способа все базисные функции

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

которые получаются из вычислимых при помощи суперпозиции или при-

митивной рекурсии. Действительно, рассмотрим суперпозицию h(x

, . . . ,

) = f(g

, . . . , x

), . . . , g

, . . . , x

)). Если есть алгоритмы для вы-

числения g

-ых и функции f, то для любого набора натуральных чисел

, . . . , m

можно последовательно вычислить значения g

-ых от этого

При желании можно рассматривать алгоритмическую сводимость какого-либо

способа задания натурального числа к десятичной записи (и наоборот) как определе-

ние ”естественности” этого способа.

набора, а потом подставить полученные значения и вычислить от них

функцию f. То, что получится, будет значением функции h на исходном

наборе. Эту процедуру можно рассматривать как описание алгоритма

для вычисления функции h. Если же функция f задается по схеме при-

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

f(0, x

, . . . , x

) = g(x

, . . . , x

)

f(t + 1, x

, . . . , x

) = h(f(t, x

, . . . , x

), t, x

, . . . , x

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

числения функции f от набора аргументов n, m

, . . . , m

будет следу-

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

для вычисления g и h, построить конечную последовательность чисел

f(0, m

, . . . , m

), f (1, m

, . . . , m

), . . . , f(n, m

, . . . , m

) длины n + 1, а за-

тем взять последний элемент этой последовательности.

Таким образом, можно утверждать, что каждая примитивно рекур-

сивная функция будет удовлетворять определению 4, то есть будет вы-

числимой. Обратное, к сожалению, не верно. Одна из причин заключа-

ется в том, алгоритмы, как мы уже отмечали, могут ”зацикливаться” и

не давать никакого результата при некоторых входных данных, а каж-

дая примитивно рекурсивная функция является всюду определенной. Но

есть и другие, более существенные причины

. В связи с этим в допол-

нение к операторам суперпозиции и примитивной рекурсии нам понадо-

бится еще один оператор.

Пусть k ∈ N и g(y, x

, . . . , x

) — (k + 1)-местная частичная функция.

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

g при помощи минимизации, если она задается следующим образом:

f(x

, . . . , x

) =











, если g( i

, x

, . . . , x

) = 0 и для всех

i < i

g(i, x

, . . . , x

) определено и

не равно нулю;

не определено, если не существует i

∈ N, удовлет-

воряющего первому условию.

Если f(x

, . . . , x

) получается из g(y, x

, . . . , x

) при помощи минимиза-

ции, то мы пишем f(x

, . . . , x

) = µy(g(y, x

, . . . , x

) = 0). Минимизация,

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

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

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

всюду определенной функции функцию, которая не является таковой.

Например, функция обычной разности x −y, неопределенная при x < y,

задается следующей формулой: x−y = µz(((y +z)

x)+(x

(y+z)) = 0).

Отметим еще такой момент: наличие y, для которого g(y, x

, . . . , x

) = 0

еще не достаточно для того, чтобы f(x

, . . . , x

) была определена; тре-

буется, чтобы для такого y при всех i 6 y значение g(i, x

, . . . , x

) тоже

являлось определенным. Например, если g(0) = 1, g(1) не определено и

g(2) = 0, то 0-местная функция µy(g(y) = 0) принимает неопределенное

значение.

Можно утверждать, что если существует алгоритм для вычисления

функции g(y, x

, . . . , x

), то функция µy(g(y, x

, . . . , x

) = 0) тоже вычис-

лима при помощи алгоритма. Этот алгоритм следующий: мы последо-

вательно вычисляем значения g(0, x

, . . . , x

), g(1, x

, . . . , x

), . . . и ждем,

когда в этой последовательности появится ноль; как только он появился,

мы объявляем номер первого нулевого члена последовательности зна-

чением функции f(x

, . . . , x

). Если нуля так и не появится, то алго-

ритм никогда не закончит свою работу и значение f(x

, . . . , x

) окажется

неопределенным. Это может произойти в двух случаях:

1. Для любого i значение g(i, x

, . . . , x

) определено и не равно нулю.

Тогда алгоритм будет вычислять все новые и новые члены после-

довательности, но так никогда и не остановится;

2. для некоторого i

значение g(i

, x

, . . . , x

) не определено, а для

всех i < i

это значение не равно нулю. Тогда алгоритм ”зависнет”

на первом таком i

, вычисляя g(i

, x

, . . . , x

), и никогда не закон-

чит свою работу, так и не вычислив, чему равны остальные члены

последовательности.

Определение оператора минимизации построено так, чтобы были учтены

обе эти возможности.

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

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

, . . . , f

такая что f

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

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

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

суперпозиции, примитивной рекурсии или минимизации.

Определение 17 Функция называется рекурсивной

, если она частич-

но рекурсивна и всюду определена.

Из приведенных выше замечаний следует, что каждая частично ре-

курсивная функция является вычислимой в самом общем смысле (со-

гласно определению 4). Обратное можно поставить под сомнение. Од-

нако до сих пор никому так и не удалось придумать пример функции,

для которой существует алгоритм вычисления, но которая не являет-

ся частично рекурсивной. Более того, все известные на данный момент

методы построения алгоритмов сводятся к трем перечисленным выше

приемам: суперпозиции, примитивной рекурсии и минимизации. В связи

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

Тезис Черча: Всякая вычислимая (в общем смысле, согласно опреде-

лению 4) частичная функция из N

в N является частично рекурсивной.

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

но им можно пользоваться. Например, если известен алгоритм вычис-

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

или в

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

частично рекурсивна. В будущем мы тоже иногда будем так поступать.

А пока попробуем выяснить, в каких отношениях тезис Черча находится

с введенным ранее тезисом Тьюринга.

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

шина Шенфилда. Машина Шенфилда состоит из бесконечного списка

пронумерованных регистров: R0, R1, . . ., каждый из которых может со-

держать произвольное натуральное число. Машина работает по програм-

ме, в ходе выполнения которой содержимое регистров может меняться.

Программа представляет собой пронумерованный список команд, каж-

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

В литературе также встречается термин ”общерекурсивная функция”, который

обозначает то же самое, что и термин ”рекурсивная функция”. Первоначально общере-

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

все члены определяющей последовательности f

, . . . , f

= f являются всюду опре-

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

тогда и только тогда, когда она рекурсивна, после чего эти термины стали употреб-

лятся как синонимы.

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

1. INC i для i ∈ N. При исполнении этой команды машина увеличива-

ет содержимое i-го регистра на 1, после чего управление переходит

к следующей команде.

2. DEC i, n для i, n ∈ N. Характер действий, совершаемых машиной

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

Ri. Если это содержимое равно нулю, то никаких изменений в ре-

гистрах не происходит, а управление передается на следующую по

списку команду. Если оно не равно нулю, то содержимое i-го ре-

гистра уменьшается на единицу, после чего управление передается

на команду с номером n.

В ходе своей работы машина выполняет последовательно команду за

командой, меняя при этом состояние регистров. На каждом шаге испол-

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

Перед началом работы управление передается на команду с номером 1,

то есть на первую команду программы. Если в ходе работы управле-

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

прекращается и машина останавливается.

Например, рассмотрим следующую короткую программу:

1 : INC 1

2 : DEC 0, 1

3 : DEC 1, 4

Работая по этой программе, машина будет исполнять по очереди первую

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

шая содержимое нулевого до тех пор, пока содержимое нулевого реги-

стра не окажется равным нулю. После этого управление будет передано

на команду с номером 3, исполнив которую, машина уменьшит содер-

жимое первого регистра на единицу и перейдет к команде с номером 4.

Поскольку такой команды не существует, то машина остановится. После

того, как программа закончит работу, в регистрах по сравнению с их пер-

воначальным состоянием произойдут следующие изменения: к содержи-

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

нулевого регистра станет равным нулю.

Заметим, что хотя машина содержит бесконечно много регистров, в

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

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

машины по этой программе и на результат работы.

Пусть P — программа для машины Шенфилда и k ∈ N. Опреде-

лим частичную k-местную функцию f

, . . . , x

). Пусть состояние ре-

гистров машины Шенфилда следующее: в регистрах R1, R2, . . . , Rk запи-

саны числа x

, . . . , x

соответственно, а во всех остальных регистрах со-

держатся нули. Пусть машина Шенфилда начинает свою работу по про-

граммме P из этого состояния регистров. Тогда полагаем f

, . . . , x

)

равным содержимому регистра R0 после окончания работы програм-

мы, если машина заканчивает работу; в противном случае полагаем, что

, . . . , x

) не определено.

Пусть k ∈ N и P — программа

. Расширим список команд для маши-

ны Шенфилда, введя так называемые макрокоманды, то есть команды

вида P (i

, . . . , i

) → j. При выполнении такой макрокоманды машина ве-

дет себя следующим образом: она берет набор из k натуральных чисел,

соответсвующих значениям регистров Ri

, . . . , Ri

и пытается вычислить

значение функции f

на этом наборе. Если это значение определено, то

она заносит его в регистр Rj, не меняя при этом содержимое других

регистров, и переходит к исполнению следующей команды. Если же зна-

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

этом никаких команд, но и не останавливаясь. Можно сказать, что ис-

полнение команды P (i

, . . . , i

) → j аналогично вызову подпрограммы,

вычисляющей функцию f

Мы говорим, что программы Q

и Q

эквивалентны, если для любого

k ∈ N частичные функции f

и f

равны.

Теорема 6 Для каждой программы, содержащей макрокоманды, суще-

ствует эквивалентная ей программа, состоящая только из стандартных

команд.

Доказательство. Покажем, как по программе, содержащей макроко-

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

торой на единицу меньше. Применяя эту процедуру к любой программе

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

ную ей программу, не содержащую макрокоманд.

Пусть программа Q состоит из команд C

, C

, . . . , C

, причем для

некоторого m

6 m C

— это команда P (i

, . . . , i

) → j. Пусть про-

грамма P состоит из n стандартных команд D

, . . . , D

и N — номер

наибольшего регистра, который упоминается в программе P . Напишем

Состоящая из стандартных команд, то есть команд вида INC i и DEC i, n.

программу Q

, которая эквивалентна Q и состоит из N +8k+n+m+4 ко-

манд F

, . . . , F

N+8k+n+m+4

. Выберем число M, которое больше чем номер

любого регистра, упоминаемого в программе Q. Необходимо для каждо-

го 1 6 s 6 N + 8k + n + m + 4 задать команду F

. Возможны следующие

случаи:

1. s < m

. Если C

— это либо команда вида INC i, либо команда

DEC i, l для l 6 m

, либо макрокоманда, то полагаем F

= C

. В

противном случае C

— это команда DEC i, l для l > m

. Полагаем

равным DEC i, l + N + 8k + n + 4.

2. s = m

+ t для t 6 N. Полагаем F

равным команде DEC M + t, s.

3. m

+ N + 8t < s 6 m

+ N + 8t + 8 для 0 6 t < k. Соответствующие

8 команд задаются следующим списком:

+ N + 8t + 1 : INC 0

+ N + 8t + 2 : DEC 0, m

+ N + 8t + 5

+ N + 8t + 3 : INC M + t + 1

+ N + 8t + 4 : INC M

+ N + 8t + 5 : DEC i

t+1

, m

+ N + 8t + 3

+ N + 8t + 6 : INC i

t+1

+ N + 8t + 7 : DEC M, m

+ N + 8t + 6

+ N + 8t + 8 : DEC i

t+1

, m

+ N + 8t + 9

4. s = m

+ N + 8k + t для 1 6 t 6 n. Если D

— это команда INC i

для некоторого i, то полагаем F

равным INC M + i. Если D

—

это команда DEC i, l для некоторого i и некоторого 1 6 l 6 n,

то полагаем F

равным DEC M + i, m

+ N + 8k + l. Наконец, если

— это команда DEC i, l для l 6∈ {1, . . . , n}, то полагаем F

равным

команде DEC M + i, m

+ N + 8k + n + 1.

5. m

+ N + 8k + n < s 6 m

+ N + 8k + n + 4. Соответствующие 4

команды задаются следующим списком:

+ N + 8k + n + 1 : DEC j, m

+ N + 8k + n + 1

+ N + 8k + n + 2 : INC j

+ 8

+ 3 : DEC

M, m

+ 8

+ 2

+ N + 8k + n + 4 : DEC j, m

+ N + 8k + n + 5

6. m

+ N + 8k + n + 4 < s 6 m + N + 8k + n + 4. Пусть t = s −

−N −8k −n −4. Действуем почти так же, как в первом случае.

Если C

— это либо команда вида INC i, либо команда DEC i, l

для l 6 m

, либо макрокоманда, то полагаем F

= C

. В противном

случае C

— это команда DEC i, l для l > m

. Полагаем F

равным

DEC i, l + N + 8k + n + 4.

Описание программы Q

закончено. Из этого описания видно, что

программа Q

содержит на одну макрокоманду меньше, чем программа

Q. Действительно, команда с номером m

заменена списком стандарт-

ных команд с номерами m

, . . . , m

+ N + 8k + n + 4. В приведенном

выше описании в пунктах 1 и 6 описана модификация команд програм-

мы Q с номерами, не равными m

. Те команды, номера которых больше

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

DEC i, n требуется изменить n на новый номер. Команды, которые встав-

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

, описаны в пунктах

2 – 5 и располагаются следующим образом. Сначала идут команды, опи-

санные в пункте 2, которые обнуляют регистры с M-го по M + N-ый.

Затем идут команды, описанные в пункте 3, которые присвают реги-

страм M + 1, . . . , M + k значения, содержащиеся в регистрах i

, . . . , i

Группа из восьми команд, приведенная в пункте 3, присваивает регистру

с номером M + t + 1 значение регистра i

t+1

, не меняя значения других

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

восьми команд в регистрах с номерами M и M + t + 1 содержатся нули.

Команды, описанные в пункте 4 — это команды программы P со сдви-

нутыми номерами регистров и переходов. Исполнив эти команды, маши-

на вычислит значение функции f

от чисел, содержащихся в регистрах

M +1, . . . , M +k и поместит результат в регистр M. Наконец, 4 команды,

описанные в пункте 5, помещают в регистр Rj число, содержащееся в ре-

гистре c номером M. Собирая все вместе, видим, что команды, которые

мы вставили в программу Q вместо команды с номером m

, выполняют

в совокупности те же действия, что и макрокоманда P (i

, . . . , i

) → j

и, следовательно, программа Q

эквивалентна Q. ¤

Скажем, что k-местная частичная функция f( x

, . . . , x

) вычислима

на машине Шенфилда, если f = f

для некоторой программы P.

Конечно, эти команды, в отличие от макрокоманды с номером m

, меняют зна-

чения некоторых регистров с номерами > M, однако эти регистры не упоминаются в

программе Q и не оказывают никакого влияния на работу машины по этой программе.

Теорема 7 Каждая частично рекурсивная функция вычислима на ма-

шине Шенфилда.

Доказательство. Частично рекурсивные функции получаются из ба-

зисных при помощи операторов суперпозиции, примитивной рекурсии и

минимизации. Значит, достаточно доказать, что класс функций, вычис-

лимых на машине Шенфилда, содержит все базисные функции и за-

мкнут относительно этих трех операторов.

Базисная функция, равная константе 0, вычисляется при помощи сле-

дующей программы:

1 : DEC 0, 1

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

не содержащей ни одной команды). Базисная функция s(x) вычисляется

при помощи программы

1 : INC 0

2 : DEC 1, 1

Наконец, базисная функция I

, . . . , x

) вычисляется программой

1 : INC 0

2 : DEC k, 1

3 : DEC 0, 4

Пусть n-местная функция f(x

, . . . , x

) вычисляется программой P , а

для 1 6 i 6 n k-местная функция g

, . . . , x

) вычисляется программой

. Тогда суперпозиция h(x

, . . . , x

) = f(g

, . . . , x

), . . . , g

, . . . , x

))

вычисляется при помощи следующей программы (с макрокомандами):

1 : P

(1, . . . , k) → k + 1

2 : P

(1, . . . , k) → k + 2

n : P

(1, . . . , k) → k + n

n + 1 : P (k + 1, . . . , k + n) → 0

Пусть k-местная функция g(x

, . . . , x

) вычисляется программой P ,

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

, . . . , x

) вычисляется программой Q и

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

, . . . , x

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

рекурсии:

f(0, x

, . . . , x

) = g(x

, . . . , x

)

f(t + 1, x

, . . . , x

) = h(f(t, x

, . . . , x

), t, x

, . . . , x

)

Тогда функция f вычисляется на машине Шенфилда по следующей про-

грамме:

1 : P (2, . . . , k + 1) → 0

2 : INC 0

3 : DEC 0, 6

4 : Q(0, k + 2, 2, . . . , k + 1) → 0

5 : INC k + 2

6 : DEC 1, 4

Наконец, пусть f(x

, . . . , x

) = µy(g(y, x

, . . . , x

) = 0) и функция g

вычисляется при помощи программы P . Тогда программа

1 : P (0, 1, . . . , k) → k + 1

2 : INC 0

3 : DEC k + 1, 1

4 : DEC 0, 5

вычисляет функцию f. ¤

Вернемся к машинам Тьюринга. Напомним, что машины Тьюрин-

га работают со словами конечного алфавита, в который не входят сим-

волы m, n, L, R. Для дальнейших рассмотрений зафиксируем алфавит

Σ = {0, 1}. Для набора натуральных чисел n

, . . . , n

через w(n

, . . . , n

)

обозначим слово этого алфавита, равное 01

0 . . . 01

. Дадим опре-

деление вычислимости на машине Тьюринга для числовой функции.

Определение 18 Частичная числовая k-местная функция f(x

, . . . , x

)

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

ма P (для машины Тьюринга), такая что для любых n

, . . . , n

∈ N:

1. если f(n

, . . . , n

) определено, то для некоторых t, l ∈ N и v ∈

(Σ ∪ {n})

∗

Com(hw(n

, . . . , n

), q

, 1i, P, t) = hv, q

, li и число единиц

в слове v равно f(n

, . . . , n

);

2. если f(n

, . . . , n

) не определено, то для всех t ∈ N если

Com(hw(n

, . . . , n

), q

, 1i, P, t) = hv, q, li, то q 6= q