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

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

Другими словами, вычислимость функции f на машине Тьюринга

при помощи программы P означает следующее. При данных n

, . . . , n

∈

N мы записываем на ленту слово 01

. . . 01

, устанавливаем головку на

первую позицию и запускаем машину работать по программе P из состо-

яния q

. Тогда если f(n

, . . . , n

) определено, то машина через некоторое

время остановится и число единиц на ленте будет равно f(n

, . . . , n

), а

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

Теорема 8 Каждая функция, вычислимая на машине Шенфилда, вы-

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

Доказательство. Пусть f(x

, . . . , x

) — частичная k-местная функ-

ция, вычислимая на машине Шенфилда по программе P

и M — неко-

торое число, которое больше чем k и больше чем номер любого регистра,

упоминаемого в программе P .

Ниже нам предстоит написать программу для машины Тьюринга Q,

моделирующую работу машины Шенфилда по программе P . Программа

Q, согласно определению программы для машины Тьюринга, для любо-

го состояния q (из списка упомянутых в ней и отличных от q

состояний)

и любого символа a ∈ Σ ∪ {n, m} должна содержать команду qa → . . ..

Однако некоторые команды программы, которую мы напишем, никогда

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

задаваемого конфигурацией hw(n

, . . . , n

), q

, 1i при произвольных нату-

ральных n

, . . . , n

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

для вычисления k-местной функции). В связи с этим мы, чтобы не пи-

сать лишнего, примем следующее соглашение: если команда qa → . . .

отсутствует в приведенном ниже списке команд, то эта команда имеет

вид qa → qR.

Пусть программа P состоит из n строк. Программа Q будет содер-

жать команды qa → . . . для a ∈ Σ ∪ {n, m} и q ∈ {q

, . . . , q

M−k+1

} ∪

, q

}∪

m=1

, . . . , q

s(m)

}. Мы считаем, что все упомянутые здесь

состояния различны. Кроме того, примем следующее соглашение: для

m > n или m = 0 запись q

обозначает состояние q

Способ, которым программа Q моделирует работу машины Шенфил-

да по программе P , заключается в следующем. Предположим, что мы

используем программу P для вычисления f(n

, . . . , n

). В процессе вы-

числения машина Шенфилда, работая по шагам, последовательно меняет

P — программа для машины Шенфилда.

содержимое своих регистров, не затрагивая регистры с номерами, боль-

шими чем M. Пусть перед выполнением шага a ∈ {1, 2, 3, . . .} содержимое

регистром с номерами от 0 до M равно r

, . . . , r

соответственно и на

шаге a исполняется команда с номером m (a).

Тогда для машины Тьюринга, начинающей работу по программе Q из

состояния, задаваемого конфигурацией hw(n

, . . . , n

), q

, 1i, существует

последовательность шагов t

< t

< . . . ее работы, такая что:

1. перед выполнением шага t

на ленте записано слово 1

0 . . . 01

;

2. перед выполнением шага t

головка находится в состоянии q

m(a)

указывает на первую ячейку ленты;

3. на шагах t

6 t < t

a+1

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

принадлежат множеству {q

m(a)

, . . . , q

m(a)

s(m(a))

Таким образом, команды программы Q, имеющие вид qa → . . . для

q ∈ {q

, . . . , q

s(m)

}, моделируют исполнение команды исходной програм-

мы P под номером m, меняя содержимое ленты машины Тьюринга в

соответствии с тем, как команда под номером m меняет содержимое реги-

стров машины Шенфилда. Если при каких-то начальных данных маши-

на Шенфилда останавливается на шаге a (то есть m(a) 6∈ {1, . . . , n}), то в

начале шага t

головка машины Тьюринга, работающей по программе Q,

оказывается в состоянии q

и машина Тьюринга переходит к исполнению

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

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

на машине Шенфилда) и машина останавливается. Кроме заключитель-

ных команд и команд, моделирующих исполнение конкретной команды

в исходной программе P , программа Q содержит так называемые под-

готовительные команды. Это команды, исполняемые на шагах t < t

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

чальным состоянием регистров машины Шенфилда.

Переходим к детальному описанию команд каждой группы.

Подготовительные команды. Эти команды подготавливают ленту ма-

шины, приводя записанные на ней данные в соответствие с содержимым

регистров машины Шенфилда перед началом работы по программе P .

1 → q

R q

n → q

0 → q

R . . .

n → q

0 q

M−k

n → q

M−k+1

0 → q

R q

M−k+1

0 → q

M−k+1

n → q

0 q

M−k+1

1 → q

M−k+1

0 → q

R q

M−k+1

m → q

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

ходясь все время в начальном состоянии q

, пока не встанет напротив

ячейки с символом n. После этого она дописывает справа M − k симво-

лов 0, перейдя в состояние q

M−k+1

. Затем она в этом состоянии движется

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

переходя в состояние q

. Содержимое ленты при этом преобразуется из

w(n

, . . . , n

) в 1

0 . . . 01

, где r

равно n

при 1 6 i 6 k и нулю в

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

Команды, моделирующие выполнение команды машины Шенфилда

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

1. Команда с номером m имеет вид INC i. Тогда список команд для

этой группы следующий:

0 → q

R q

i+2

1 → q

i+3

1 → q

R q

i+3

0 → q

i+1

0 → q

R q

i+3

1 → q

i+1

1 → q

R q

i+4

0 → q

i+2

. . . q

i+4

1 → q

i+2

0 → q

i+1

R q

i+1

n → q

i+5

1 → q

R q

i+2

n → q

i+5

i+1

0 → q

i+4

1 q

i+5

0 → q

i+5

i+1

1 → q

i+3

1 q

i+5

1 → q

i+5

i+2

0 → q

i+4

0 q

i+5

m → q

m+1

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

ся вправо, отсчитывая i нулей и переходя в состояние q

i+1

. Затем

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

сдвигая содержимое следующих ячеек на одну позицию вправо. За-

кончив сдвиг, она переходит в состояние q

i+5

, из которого движется

влево ”до упора”, а потом переходит на первую позицию, меняя со-

стояние на q

m+1

2. Команда с номером m имеет вид DEC i, l . Список команд для этой

группы таков:

0 → q

R q

i+2

1 → q

i+2

L q

i+6

1 → q

i+3

1 → q

R q

i+2

m → q

m+1

R q

i+6

0 → q

i+6

0 → q

R q

i+1

1 → q

i+3

1 q

i+4

n → q

i+7

1 → q

R q

i+3

0 → q

i+4

R q

i+7

0 → q

i+8

. . . q

i+3

1 → q

i+4

R q

i+7

1 → q

i+8

0 → q

i+1

R q

i+4

0 → q

i+5

L q

i+8

n → q

i+8

1 → q

R q

i+4

1 → q

i+6

L q

i+8

0 → q

i+8

i+1

0 → q

i+2

L q

i+5

0 → q

i+3

R q

i+8

1 → q

i+8

i+2

0 → q

i+2

L q

i+5

1 → q

i+5

0 q

i+8

m → q

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

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

гается вправо, отсчитывая i нулей и переходя в состояние q

i+1

Дальнейшие действия зависят от содержимого ячейки, на которую

указывает головка. Если в этой ячейке находится ноль (то есть со-

держимое i-го регистра машины Шенфилда равно нулю), то голов-

ка машины Тьюринга переходит в состояние q

i+2

, идет влево ”до

упора”, а затем сдвигается на одну позицию вправо, переходя в со-

стояние q

m+1

. Если же головка в состоянии q

i+1

указывает на ячей-

ку, в которой записана единица, то она переходит в состояние q

i+3

затем стирает содержимое этой ячейки, сдвигая все ячейки справа

от этой на одну позицию влево и постепенно перемещаясь вправо.

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

i+8

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

гается вправо на одну позицию и переходит в состояние q

Заключительные команды. После того, как работа машины Шенфил-

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

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

и далее — еще нули и единицы, отображающие состояние регистров ма-

шины Шенфилда, отличных от R0. Эти лишние символы надо стереть.

Для этого предназначена следующая группа команд:

1 → q

R q

1 → q

n q

n → q

0 → q

0 q

n → q

R q

1 → q

0 → q

n q

n → q

L q

m → q

Действия, производимые этими командами, очевидны.

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

которые от них требуются. Собирая вместе все команды из различных

групп, получаем программу Q, вычисляющую на машине Тьюринга функ-

цию f. ¤

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

машине Тьюринга.

Доказательство. Это прямое следствие теорем 7 и 8. ¤

На самом деле мы доказали чуть больше, чем требовалось. Пусть

f(x

, . . . , x

) — частично рекурсивная функция и P — программа для

вычисления функции f, которую мы построили в теореме 8. Если для

, . . . , n

∈ N f(n

, . . . , n

) определено и мы запустим машину Тьюринга

работать по этой программе, записав на ленте слово w(n

, . . . , n

), уста-

новив головку на первую позицию и приведя ее в состояние q

, то через

некоторое время машина остановится, придя в состояние q

, и на ленте

окажется записанным некоторое слово v. Нам было бы достаточно, чтобы

число единиц в слове v было равно f(n

, . . . , n

), причем эти единицы мо-

гут быть раскиданы по ленте как угодно, перемежаясь символами 0 и n.

Однако у нас эти единицы идут подряд, одна за другой, начиная с первой

ячейки; нулей на ленте нет, а головка находится в первой позиции. Если

вспомнить определение 13, то этот результат можно интерпретировать

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

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

ле определения 4. У нас есть два конструктивных пространства: N

N, а также функция f из первого пространства во второе. Эта функция

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

бора аргументов дает описание значения функции на этих аргументах.

Можно зафиксировать следующие описания: набор чисел n

, . . . , n

опи-

сывается словом w(n

, . . . , n

), а натуральное число n — словом 1

. Тогда

реализацией требуемого алгоритма будет программа для машины Тью-

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

7 и 8.

В настоящий момент мы собираемся определить кодировки конфигу-

раций и программ машин Тьюринга. Позже мы введем общее понятие

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

мерации. А пока скажем, что кодировка объекта — это способ его задания

при помощи натуральных чисел.

Кодирование конфигураций. Мы продолжаем работать с алфа-

витом Σ = {0, 1}. Вспомним, что конфигурация — это тройка hw, q

, li,

где w — слово алфавита Σ ∪ {n}, не заканчивающееся на n, q

— состоя-

ние головки, а l — натуральное число (номер ячейки ленты, на которую

указывает головка). Конфигурации мы будем кодировать тройками на-

туральных чисел hm

, m

i, где m

— код слова w, m

— код состояния

, а m

— код числа l. Кодом числа l будет само число l (то есть m

= l).

Код состояния q

— это номер этого состояния, то есть число i. Наконец,

кодом слова w = a

. . . a

назовем число p(1)

p(2)

. . . p(k)

, где для

1 6 i 6 k ε

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











0, a

= n;

1, a

= 0;

2, a

= 1.

Из единственности разложения каждого натурального числа на простые

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

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

Кодирование программ. Задавая кодировку программ, мы ставим

перед собой более сложную задачу, чем в предыдущем случае. Мы хотим,

чтобы наша кодировка удовлетворяла следующим трем требованиям:

1. Код каждой программы — это некоторое натуральное число (а не

тройка чисел, как в предыдущем случае).

2. Каждая программа имеет хотя бы один код (мы допускаем, что

разные числа могут кодировать одну и ту же программу).

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

Для задания кодировки поступим следующим образом: опишем, как по

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

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

Пусть k ∈ N. Программа, которую это число кодирует, содержит ко-

манды вида q

a → . . ., где a — символ алфавита {0, 1, n, m}, а q

— эле-

мент множества {q

, q

, . . . , q

} для некоторого s > 1. Значит, по коду k

мы должны уметь получать число s. Положим s = l(k) + 1, рассматри-

вая ”левую часть” числа

k как код для множества состояний головки.

”Правую часть” r(k) мы интерпретируем как код для списка команд про-

граммы.

Сопоставим каждой паре hq

, ai, где i 6 s и a ∈ {0, 1, n, m} нату-

ральное число β(q

, a) следующим образом: β(q

, a) = c(i, ε(a)), где ε(a)

определяется так:

ε(a) =











0, a = n

1, a = 0

2, a = 1

3, a = m

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

Число r(k) + 1 единственным способом раскладывается на простые мно-

жители. Поступим следующим образом: показатель степени при простом

числе p(β(q

, a)) в разложении r(k) + 1 будем рассматривать как число,

кодирующее правую часть команды q

a → . . ..

Итак, пусть t — это максимальное натуральное число, такое что

p(β(q

, a))

делит r(k) + 1. Соответствующая числу t команда програм-

мы, кодом которой является число k, имеет вид q

a → q

b, где j 6 s и

b ∈ {0, 1, n, L, R}. ”Левую часть” l(t) числа t будем интерпретировать как

код состояния q

, а ”правую часть” r(t) — как код символа b. Примем

следующие правила кодирования: j равно остатку от деления числа l(t)

на s + 1 (то есть j = rest(l(t), s + 1)), а

b =











n, rest(r(t), 5) = 0 и a 6= m

0, rest(r(t), 5) = 1 и a 6= m

1, rest(r(t), 5) = 2 и a 6= m

L, rest(r(t), 5) = 3 и a 6= m

R, rest(r(t), 5) = 4 или a = m

Описание кодировки закончено. Легко видеть, что каждому натураль-

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

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

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

Имеем k = c(x, y) для некоторых единственных x и y. Число x мы называем

”левой частью” числа k, а число y — ”правой частью”.

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

найдется натуральное число, которое является ее кодом. Действительно,

если есть программа, написанная для множества состояний {q

, q

. . . q

то ее кодом будет число c(s − 1, x − 1), где x вычисляется так: надо для

каждой команды q

a → . . ., взять число p(β(q

, a)), возвести его в сте-

пень t, где t — какой-либо из кодов правой части команды, а затем взять

произведение этих степеней по всем командам программы.

Определим три четырехместные функции Step

, Step

и Step

. Пусть

, m

i — произвольная тройка натуральных чисел и n — натураль-

ное число. Пусть P — программа, кодом которой является число n. Воз-

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

1. Тройка hm

, m

i не является кодом никакой конфигурации либо

, m

i — код конфигурации hw, q

, li, но состояние q

не входит

в число состояний, с которыми работает программа P (то есть i >

l(n)+1). Полагаем Step

(n, m

, m

) = m

, Step

(n, m

, m

) =

и Step

(n, m

, m

) = m

2. Тройка hm

, m

i является кодом конфигурации hw, q

, li и i 6

l(n) + 1. Тогда определена конфигурация hv, q

, ki, равная

Step(hw, q

, li, P), которая отражает состояние машины Тьюринга,

получающееся после одного шага работы машины по программе P

из состояния, соответсвующего конфигурации hw, q

, li. Конфигура-

ция hv, q

, ki имеет код, равный hm

, m

i. Полагаем Step

(n, m

, m

) = m

, Step

(n, m

, m

) = m

и Step

(n, m

, m

) =

Лемма 3 (о кусочном определении функции) Пусть P

, . . . , x

. . ., P

, . . . , x

) — примитивно рекурсивные предикаты, такие что для

любых n

, . . . , n

∈ N существует единственное 1 6 i 6 n, для которого

предикат P

, . . . , n

) истинен. Пусть f

, . . . , x

), . . ., f

, . . . , x

) —

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

f(x

, . . . , x

) =











, . . . , x

), P

, . . . , x

)

, . . . , x

), P

, . . . , x

)

. . . . . .

, . . . , x

), P

, . . . , x

)

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

Доказательство. f(x

, . . . , x

) =

i=1

, . . . , x

). ¤

Лемма 4 Функции Step

, Step

и Step

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

Доказательство. Ясно, что тройка hm

, m

i является кодом неко-

торой конфигурации тогда и только тогда, когда для любого i

log(p(i), m

) 6 2, log(p(0), m

) = 0 и m

6= 0. Легко заметить, что для

любого i p(i) > i и что если log(p(i), m

) > 2, то p(i) < m

. В связи с этим

условие, при выполнении которого функции Step

(1 6 i 6 3) задаются в

пункте 2 приведенного выше определения, выполняется тогда и только

тогда, когда на наборе n, m

, m

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

дикат S(y, x

, x

) = (x

6 l(y) + 1) & (x

6= 0) & ((µi 6 x

)(log(p(i), x

) >

2) = x

+ 1) & (log(p(0), x

) = 0).

Введем несколько примитивно рекурсивных функций:

i(x

, x

) = x

a(x

, x

) =

(

3, x

= 0

log(p(x

), x

> 0

t(y, x

, x

) = log(p(c(i(x

, x

), a(x

, x

))), r(y) + 1)

j(y, x

, x

) = rest(l(t(y, x

, x

)), l(y) + 2)

b(y, x

, x

) =

(

rest(r(t(y, x

, x

)), 5), x

> 0

4, x

= 0

Смысл этих функций таков. Пусть n — номер программы P и hm

, m

i — код конфигурации hw, q

, ki, причем i 6 l(n)+1. Рассмотрим состо-

яние машины, соответствующее этой конфигурации. В этом состоянии

головка находится в состоянии q

и указывает на k-ую ячейку ленты,

в которой записан некоторый символ a ∈ {0, 1, m, n}. В программе P

есть команда q

a → q

b, где b ∈ {n, 0, 1, L, R}. Тогда i = i(m

, m

a(m

, m

) — код символа a, t(n, m

, m

) — код правой части ко-

манды q

a → q

b, j = j(n, m

, m

) и b(n, m

, m

) — код симво-

ла b. Пусть T(y, x

, x

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

S(y, x

, x

) & (i(x

, x

) 6= 0). Окончательно получаем

Step

(y, x

, x

) =











, (b(y, x

, x

) 6 2) ∨ ¬T (y, x

, x

)

1, (b(y, x

, x

) = 3) & T (y, x

, x

)

+ 1, (b(y, x

, x

) > 4) & T (y, x

, x

);

Step

(y, x

, x

) =

(

, ¬T (y, x

, x

)

j(y, x

, x

), T (y, x

, x

);

Step

(y, x

, x

) =

(

, (b(y, x

, x

) > 3) ∨ ¬T (y, x

, x

)

γ(y, x

, x

), (b(y, x

, x

) 6 2) & T (y, x

, x

где γ(y, x

, x

) = div(x

, p(x

)

a(x

)

) · p(x

)

b(y,x

)

. ¤

Введем теперь три пятиместные функции Com

, Com

. Для

1 6 i 6 3 полагаем





Com

(y, x

, x

, 0) = x

Com

(y, x

, x

, t + 1) = Step

(y, Com

(y, x

, x

, t),

Com

(y, x

, x

, t), Com

(y, x

, x

, t))

Смысл этих функций ясен. Если hm

, m

i — код конфигурации C,

n — натуральное число, кодирующее программу P , и программа P при-

менима к конфигурации C (то есть m

6 l(n) + 1), то для любого t

hCom

(n, m

, m

, t), Com

(n, m

, m

, t), Com

(n, m

, m

, t)i —

код конфигурации Com(C, P, t), отражающей состояние машины, кото-

рое получается из состояния, задаваемого конфигурацией C, после t ша-

гов работы по программе P .

Лемма 5 Функции Com

, Com

и Com

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

Доказательство. Рассмотрим трехместную функцию α(y, x, t), кото-

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

α(y, x, 0) = x

α(y, x, t + 1) = 2

(y,α(y,x,t))

· 3

(y,α(y,x,t))

· 5

(y,α(y,x,t))