189

Рис. 6.3. Повторение алгоритмов

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

Теорема 6.4. Повторение нормального алгоритма, управляемое нормальным алгоритмом, есть нормальный алгоритм.

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

§ 7. Машина Тьюринга

Стремясь найти точное определение понятия алгоритма, Тьюринг выделил некоторый класс абстрактных машин, о которых высказал предположение, что они пригодны для осуществления любой "механической" вычислительной процедуры. Эти машины называются теперь в честь их изобретателя машинами Тьюринга.

S0

Пусть имеется лента, потенциально

q0

бесконечная в обе стороны* и разделенная

на ячейки (квадраты), см. Рис. 6.4.

Рис. 6.4.

Потенциальная

бесконечность

ленты

понимается в том смысле, что в каждый

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

Имеется некоторое конечное множество символов S0,S1,..,Sn, которое называется алфавитом машины. В каждой ячейке может быть записан только один из символов - букв алфавита машины.

Машина обладает некоторым конечным множеством внутренних состояний {q0,q1,...,qm}. В каждый данный момент времени машина находится только в одном из этих состояний. Считаем, что внутренним

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

190

состоянием q0 обладает каждая машина и q0 называется начальным состоянием.

Машина имеет читающую головку, которая в каждый данный момент времени находится на одном из квадратов ленты и воспринимает символ, записанный на этом квадрате. Будем предполагать, что среди символов S0,S1,..,Sn имеется символ, означающий пустой квадрат, например, S0. Положим, что символ S0 принадлежит алфавиту каждой машины Тьюринга и S0 не может быть записан ни в каком квадрате ленты. Когда мы пишем, что читающая головка обозревает квадрат с символом S0 или записывает в квадрат символ S0, то имеем в виду, что читающая головка соответственно обозревает пустой квадрат (воспринимая его как S0) или оставляет квадрат без символов (воспринимая его как S0). Машина действует не непрерывно, а лишь в дискретные моменты времени.

Если в какой-то момент времени t читающая головка воспринимает квадрат (т.е. стоит на квадрате), содержащий символ Si, и машина находится во внутреннем состоянии qj, то действие машины определено, и она совершает один из следующих четырех действий:

1)головка стирает символ Si и записывает на том же квадрате символ Sk;

2)головка перемещается в соседний слева квадрат;

3)головка перемещается в соседний справа квадрат;

4)машина останавливается.

В случаях 1)-3) машина переходит во внутреннее состояние qr и готова к действию в следующий момент времени t+1.

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

1)qj Si Sk qr;

2)qj Si L qr;

3)qj Si R qr.

Любая машина имеет конечное (непустое) множество команд.

Машина останавливается, если она находится в некотором внутреннем состоянии qj, читающая головка обозревает какой-то символ Sk, а среди команд машины нет команды, начинающейся с qjSk.

Если на ленте имеется какое-нибудь слово Р (в частности, пустое слово), читающая головка помещена на квадрат с первой левой буквой слова Р и машина приведена во внутреннее состояние q0, то машина начинает оперировать на ленте: ее головка стирает и пишет символы и перемещается из одного квадрата в другой (соседний). Если при этом машина когда-нибудь останавливается, то находящееся в момент остановки слово на ленте считается результатом применения машины Т к данному слову Р и обозначается через Т(Р). Если процесс переработки машиной Т слова Р бесконечен, то говорят, что машина Т не применима к слову Р.

191

§ 8. Задание машины Тьюринга

Машина Тьюринга Т считается заданной, если задано непустое конечное множество упорядоченных четверок символов (команд), удовлетворяющих условиям:

а) каждая четверка символов принадлежит к одному из трех типов команд, приведенных выше (в § 7),

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

в) среди команд любой машины всегда есть хотя бы одна команда, начинающаяся с q0.

Множество всех символов типа Sm, входящих в команды машины, называется алфавитом заданной машины, а входящие в эти команды символы qi называются внутренними состояниями заданной машины Т.

Считаем, что в исходном (начальном) состоянии машина обладает внутренним состоянием q0.

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

Рассмотрим несколько примеров.

1. Пусть задана машина Т командами:

q01Rq1 q1S01q0,

а на ленте записано слово Р=1, см. Рис.6.5. Легко убедиться, что машина Т, начав работу с первой буквы слова Р, приписывает к нему слева по одной букве 1 на каждом шаге, никогда при этом не останавливаясь. Следовательно, эта машина неприменима к слову Р.

2. Машина, заданная командами:

q0S0Rq0

q0S1Rq0

q0S2Rq0

q0SkRq0

………

q011q1,

где ни одно из Si (1≤ i≤ k) не совпадает с символом 1, двигается по ленте вправо, пока не встретит вхождение (если такое вообще имеется) символа 1, после чего останавливается.

3. Машина Т, заданная командами

q0aRq0 q0bRq0 q0S0aq1,

как легко убедиться, приписывает к любому слову Р алфавита {a,b} справа букву а и останавливается.

192

§9. Алгоритм Тьюринга. Вычислимость по Тьюрингу

Скаждой машиной Тьюринга можно связать некоторый алгоритм AT,A в алфавите А машины Т. Возьмем произвольное слово Р алфавита А и запишем его слева направо в квадратах чистой ленты, причем так, чтобы первая (самая левая) буква Р находилась под читающей головкой. Приведем машину Т во

внутреннее состояние q0. Машина начинает работать. Если она когда-нибудь остановится, то появившееся в результате на ленте слово алфавита А является

значением алгоритма AT,A. Такой алгоритм AT,A называется алгоритмом Тьюринга.

Будем говорить, что машина Тьюринга Т с алфавитом А, включающим 1

и*, частично вычисляет частичную арифметическую функцию f(x1,x2,...,xn), если для любых натуральных k1,k2,...,kn и некоторых r и m имеем:

A	(							) = S r								S m ,	(Si	= S S ...S		),
		k	1	,k	2	,...,k	n		f ( k	1	,k	2	,...,k	n	)				0
T ,A								0							0		0	0 0
																		14243

i раз

тогда и только тогда, когда определена хотя бы одна из частей этого равенства. Это означает, что применение алгоритма Тьюринга AT,A к слову

( k1 ,k2 ,...,kn ) даст слово, означающее с точностью до слов S0r и S0m значение

функции f(k1,k2,...,kn) (S0 - интерпретируется как изображение пустого квадрата ленты).

Арифметическая функция f(x1,x2,...,xn) называется вычислимой по Тьюрингу, если для любых натуральных k1,k2,...,kn и некоторых r и m имеем:

A	(							) = S r								Sm ,	(Si	= S S ...S		).
		k	1	,k	2	,...,k	n		f ( k	1	,k	2	,...,k	n	)				0
T ,A								0							0		0	0 0
																		14243

i раз

Это означает, что применение алгоритма Тьюринга AT,A к слову ( k1 ,k2 ,...,kn ) даст слово, означающее с точностью до слов S0r и S0m значение функции

f(k1,k2,...,kn), т.е. существует машина Тьюринга, вычисляющая эту функцию для любых значений её аргументов.

Пример. Рассмотрим всюду определенную функцию сложения f(x,y)=x+y. Покажем, что эта функция вычислима по Тьюрингу. Для этого построим машину Тьюринга:

q0 1 S0 q0 q0 S0 R q1 q1 1 R q1 q1 * 1 q2 q2 1 R q2 q2 S0 L q3 q3 1 S0 q3.