193

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

( m,n )=11...1*11...1 в слово 11...1, а последнее слово означает

m+1 n+1

m+n+1

число m+n, следовательно, эта машина Тьюринга вычисляет функцию х+у. Итак, функция х+у вычислима по Тьюрингу.

Из разнообразия возникает совершенная гармония.

Гераклит

§ 10. Связь между машинами Тьюринга и нормальными алгоритмами

Теорема 6.5. Пусть Т - машина существует нормальный алгоритм B относительно А алгоритму Тьюринга AT,A.

Тьюринга с алфавитом А. Тогда над А, вполне эквивалентный

.

Доказательство. Каждая конкретная машина Тьюринга содержит конечное число команд вида 1)-3) (§ 7). Выпишем сначала для всех команд вида qjSiSkqr (если они есть) машины Т формулы подстановки qjSi→qrSk. При этом порядок этих формул подстановок друг относительно друга не существенен, ибо никакие две команды машины Т не имели совпадающими первые два символа. Далее для каждой команды вида qjSiLqr (если она есть) выпишем всевозможные формулы подстановки вида SlqjSi→qrSlSi, где Sl A, и формулу подстановки qjSi→qrS0Si. Затем для каждой команды вида qjSiRqr (если она есть) выпишем всевозможные формулы подстановки qjSiSl→SiqrSl, где Sl A, и формулу подстановки qjSi→SiqrS0. Наконец, выпишем всевозможные формулы подстановок qi→•Λ, где qi - внутреннее состояние заданной машины Т, и формулу подстановки Λ→q0. Полученная таким образом таблица (схема) формул подстановок определяет некоторый нормальный алгоритм B над А.

Покажем, что полученный нормальный алгоритм B вполне эквивалентен относительно алфавита А алгоритму Тьюринга AT,A , т.е. оба алгоритма одинаковым образом преобразуют любое слово Р алфавита А. Для этого возьмем произвольное слово Р в алфавите А, пусть, например, Р=Sk1,Sk2,...Skm, где Ski A. Машина Тьюринга находится сначала во внутреннем состоянии qΟ и обозревает символ Sk1. Дальнейшие ее действия определены ее командами. Из подстановок алгоритма B к слову Р будет сначала применима только

последняя подстановка, в результате которой получим слово
q0 Sk1,Sk2,...Skm	(1)

194

Если среди команд машины Т имеется команда, по которой стирается буква

Sk1 и заменяется, например, буквой Sj(Sj A), т.е. имеется команда q0Sk1Sjqr, то по подстановке q0Sk1→qrSj алгоритм преобразует слово (1) в слово

qr Sj Sk2...Skm.

Если же машина Т не изменяет буквы Sk1, а читающая головка движется,

например, вправо по команде q0Sk1Rqr, то по подстановке q0Sk1Sl→ Sk1qrSl (Sl A) алгоритма B из (1) получим

Sk1qrSk2...Skm.

Ясно, что и любому другому такту машины Т будет соответствовать такое же преобразование слова с помощью алгоритма B, за исключением того, что при преобразовании с помощью B в слове у нас всегда имеется некоторое qi, которого нет на ленте машины. Однако в конце преобразования алгоритм B своей подстановкой qi→•Λ уберет эту лишнюю букву. Итак,

P в А : AT,A(Р) B(Р),

что и требовалось доказать.

Следствие 6.1. Всякая частично вычислимая (вычислимая) по Тьюрингу функция является частично вычислимой (вычислимой) по Маркову функцией.

Доказательство. Пусть функция f(x1,x2,...,xn) вычислима по Тьюрингу и ее вычисляет машина Тьюринга Т с алфавитом А, содержащим 1 и *. Это означает, что для любых натуральных чисел k1,k2,...,kn найдутся такие слова

R1 и R2 (возможно, пустые) в алфавите {S0}, что AT,A ( k1 ,k2 ,...,kn )

=R1 f ( k1 ,k2 ,...,kn ) R2. В силу доказанной теоремы 6.5 существует нормальный

алгоритм B над А, вполне эквивалентный относительно А алгоритму AT,A, т.е. для любых натуральных чисел k1,k2,...,kn имеем:

AT,A((

)) B((

)) R1

R2.

(2)

k1 ,k2 ,...,kn

k1 ,k2 ,...,kn

f ( k1 ,k2 ,...,kn )

Для того, чтобы функция была частично вычислимой по Маркову,

нужно, чтобы

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

преобразует

(

)

в

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

k1

,k2 ,...,kn

f ( k1 ,k2 ,...,kn )

(

)

в R1

R2. Надо как-то изменить алгоритм, чтобы он

k1

,k2 ,...,kn

f ( k1 ,k2 ,...,kn )

убирал слова R1 и R2. Пусть B1 - нормальный алгоритм над {1,*,S0}, стирающий все вхождения S0 перед первым вхождением 1 или * во всяком слове в алфавите {1,*,S0}. Такой алгоритм можно задать схемой:

195

α S0 →αα1 →•1 B1 = α→•

α →•ΛΛ→α

Пусть B2 - нормальный алгоритм над {1,*,S0}, который стирает все вхождения S0 после последнего вхождения 1 или * во всяком слове в алфавите {1,*,S0}. Например, B2 можно задать схемой:

α→ αα1 →1α

B2 = αS0 →αα →•Λ

Λ→α

Построим композицию алгоритмов B, B1 и B2: C=B2•B1•B. По доказанной теореме 6.1, алгоритм С является нормальным алгоритмом, как

композиция			нормальных алгоритмов. Для любых натуральных чисел
k1,k2,...,kn имеем
B((k1,k2 ,...,kn )) AT, A ((k1,k2 ,...,kn )) R1
								f (k1,k2 ,...,kn )R2 .
где R1 и R2			- некоторые слова в {S0}. Далее
B1 (R1			(k1,k2 ,...,kn )R2 )=
		f			f (k1,k2 ,...,kn )R2 ;
B2 (	f (k1 ,k2 ,...,kn )R2 )=
				f (k1 ,k2 ,...,kn ).
Отсюда видно, что f есть частично вычислимая по Маркову функция, ее
вычисляет нормальный алгоритм C .

Теорема 6.6. (обратная теореме 6.5).Пусть B- нормальный алгоритм в алфавите А, не содержащем S0 и δ. Тогда существует такая машина Тьюринга

Т, что алгоритм Тьюринга AT,A {Sо,δ} в алфавите A {S0,δ} обладает следующим свойством: для всякого слова Р в А алгоритм AT,A {Sо,δ} применим к Р тогда и

только тогда, когда к Р применим алгоритм B и при этом AT,A {So,δ}(P) имеет
вид S r B(P)Sm , где r и m целые неотрицательные числа, а Sk = S				0	S ...S	0	.
0	0	0			0
			14243

k раз

Согласно сформулированной теореме значения алгоритмов B и AT,A {So,δ} формально различны, так как для машины Тьюринга S0 есть символ пустого квадрата, а в нормальном алгоритме B S0-буква, равноправная с любой другой буквой. Но с точностью до символов S0, которые могут стоять справа и слева от результирующего слова, алгоритмы B и AT,A {So,δ} вполне эквиваленты. Теорему принимаем без доказательства.

196

Следствие 6.2. Всякая частично вычислимая (вычислимая) по Маркову функция частично вычислима (вычислима) по Тьюрингу.

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

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

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

«Знаете что, скрипка? Мы ужасно похожи: Я вот тоже ору -

а доказать ничего не умею!» В. Маяковский

§ 11. Основная гипотеза теории алгоритмов (принцип нормализации или тезис Черча)

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

Для всякого алгоритма В в алфавите А существует вполне эквивалентный ему нормальный алгоритм С над А, т.е.

P в А: В(Р) С(Р).

Иначе эта гипотеза формулируется так.

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