Текст книги "Новый ум короля: О компьютерах, мышлении и законах физики"
Автор книги: Роджер Пенроуз
Жанры:
Философия
,сообщить о нарушении
Текущая страница: 7 (всего у книги 47 страниц)
Универсальная машина Тьюринга
Я еще не затрагивал понятия универсальноймашины Тьюринга. Лежащий в ее основе принцип понять нетрудно, хотя детали могут быть сложны. Основная идея состоит в том, чтобы закодировать команды для произвольной машины Тьюринга Тв виде последовательности нулей и единиц, которую можно записать на ленте. Эта запись используется как начальная часть входных данных для некоторой особоймашины Тьюринга U, называемой универсальной, которая затем обрабатывает остальную часть ленты в точности так, как это сделала бы машина Т. Универсальная машина Тьюринга – это универсальный имитатор. Начальная часть ленты дает универсальной машине Uвсю информацию, необходимую для точной имитации любой машины Т!
Чтобы показать, как это может быть реализовано, нам потребуется какая-нибудь система нумерациимашин Тьюринга. Рассмотрим список инструкций, определяющих произвольную машину Тьюринга, например, одну из описанных выше. Мы должны в соответствии с некоторыми четкими правилами представить эти инструкции в виде последовательностей нулей и единиц. Это можно сделать, например, с помощью процедуры «сокращения», которую мы использовали ранее. Тогда, если мы закодируем символы R, L, STOP , «стрелка» (→) и «запятая», скажем, числами 2, 3, 4, 5 и 6 соответственно, то мы сможем записать их в виде «сокращений» 110, 1110, 11110, 111110 и 1111110. Цифры 0 и 1, кодируемые, соответственно, как 0и 10, могут быть использованы для записи строк этих символов, входящих в таблицу действий машины Тьюринга. Нам не нужны различные обозначения для «жирных» цифр 0и 1и для остальных цифр в таблице, поскольку расположение «жирных» цифр в конце двоичного кода является достаточным отличительным признаком. При этом 110 1, например, будет читаться как двоичное число 1101, представляемое на ленте последовательностью 1010010. в частности, 0 0будет читаться как 00, что без всякой двусмысленности можно закодировать как 0или вовсе опустить. Можно существенно сэкономить, если не кодировать «стрелки» и непосредственно предшествующие им символы, а воспользоваться цифровым упорядочением команд, позволяющим определить, какими должны быть эти символы. Правда, для этого надо убедиться в отсутствии «дырок» в получившемся порядке и добавить, где требуется, «немые» команды. (Например, машина Тьюринга XN +1не имеет команды, соответствующей коду 110 0, поскольку такая комбинация в ходе ее работы никогда не встречается. Следовательно, мы должны ввести в список команд немую команду, скажем 110 0 → 0 0R, которая не вызовет каких бы то ни было изменений в работе машины. Сходным образом мы должны добавить немую команду 10 1 → 0 0Rв список команд машины XN х 2.) Без таких «немых» команд кодирование последующих команд было бы нарушено. Как можно видеть, на самом деле мы не нуждаемся и в запятой в конце каждой команды, поскольку символов Lи Rвполне достаточно для отделения команд друг от друга. Поэтому мы просто будем использовать такую систему кодирования:
0для 0 или 0,
10для 1 или 1,
110для R,
1110для L,
11110для STOP.
В качестве примера выпишем команды для машины Тьюринга XN +1(с дополнительной немой командой 110 0 → 0 0R). Опуская стрелки, цифры, непосредственно предшествующие им, и запятые, получим
Мы можем улучшить полученный результат, если опустим все 0 0и заменим каждые 0 1просто единицей в соответствии с тем, что говорилось ранее. Тогда мы получим строку символов
которая на ленте записывается как последовательность
Есть еще два способа немного сэкономить. Во-первых, всегда можно удалить код 110в начале записи (вместе с бесконечным участком пустой ленты, предшествующим этому коду). Он обозначает последовательность 0 0R, соответствующую начальной команде 0 0 → 0 0R, которую я до сих пор неявно считал общей для всех машин Тьюринга, поскольку она необходима для того, чтобы устройство, начав работу в произвольной точке слева от начала записи на ленте, могло перемещаться вправо до тех пор, пока не встретит первую непустую клетку. Во-вторых, точно так же всегда можно удалить код 110(и неявную бесконечную последовательность нулей, которая, по предположению, следует за ним) в конце записи, поскольку этой кодовой последовательностью должно заканчиваться описание любой машины Тьюринга (во всех случаях список команд заканчивается командой R, Lили STOP ). Получающееся двоичное число– это номер машины Тьюринга, который для XN + 1будет выглядеть так:
В обычной десятичной записи этот номер равен
450813704461563958982113775643437908.
Иногда машину с номером n мы, не вполне точно, будем называть n-ймашиной Тьюринга и обозначать ее T n . В этом случае XN +1становится
450813704461563958982113775643437908 – й
машиной Тьюринга!
Кажется поразительным факт, что нам надо пробежать так долго вдоль «списка» машин Тьюринга, чтобы найти машину, выполняющую такую тривиальную операцию, как прибавление единицы к натуральному числу (в расширенном двоичном представлении). (Я не думаю, что моя система кодирования была в целом настолько неэффективна, хотя в ней и есть еще возможности для незначительных улучшений.) В действительности, есть машины Тьюринга и с меньшими номерами, которые представляют интерес, например UN +1с двоичным номером
101011010111101010,
который в десятичной записи превращается всего лишь в 177 642. Значит, особенно тривиальная машина UN +1, которая просто дописывает 1единицу в конце последовательности единиц, является 177 642– ймашиной Тьюринга. Интересно, что «умножение на два» в списке машин Тьюринга попадает где-то между этими двумя машинами, причем и в унарном, и в расширенном двоичном представлении: номер XN х 2равен 10 389 728 107, а номер UN х 2– 1492 923 420 919 872 026 917 547 669.
Наверное, принимая во внимание величины этих номеров, уже не вызовет удивления тот факт, что абсолютное большинство натуральных чисел не соответствует ни одной рабочей машине Тьюринга. Приведем перечень первых тринадцати машин Тьюринга в соответствии с принятой нумерацией:
Из этих машин T 0 просто перемещается вправо, стирая все, что ей попадается на пути, никогда не останавливаясь и не меняя направления движения. Машина Т 1 выполняет в сущности ту же операцию, но более громоздким путем, отступая на шаг назад каждый раз, когда она стирает очередную единицу на ленте. Так же как и T 0 , машина T 2 двигается вправо, никогда не останавливаясь, но относится к ленте более «почтительно», попросту оставляя всю информацию нетронутой. Эти машины не могут использоваться в качестве машин Тьюринга, поскольку никогда не останавливаются. T 3 – первая в этом списке «правильная» машина: она скромно прекращает действие после того, как изменяет первую (самую левую) единицу на нуль. T 4 сталкивается с серьезной проблемой. Найдя первую единицу на ленте, она переходит во внутреннее состояние, которое нигде не описано, и, следовательно, машина не имеет никаких команд для следующего шага. С той же проблемой сталкиваются T 8, T 9и T 10 . С T 7 возникают трудности еще более фундаментального характера. Строка нулей и единиц, которой она представляется, включает последовательность из пяти единиц: 110111110. Интерпретации этой последовательности не существует, поэтому T 7 намертво застревает сразу же, как только доходит до первой единицы. (Я буду называть T 7 , равно как и любую другую машину T n , двоичное расширенное представлений которой содержит более четырех единиц, некорректно определенной .) Машины T 5, T 6и T 12 испытывают те же трудности, что и T 0, T 1, T 2: они просто никогда не останавливаются. Все эти машины – T 0, T 1, T 2, T 5, T 6, T 7, T 8, T 9, T 10и T 12 – совершенно бесполезные устройства! Только T 3 и T 11 являются функциональными машинами Тьюринга, да и то не слишком интересными. Причем T 11 даже скромнее, чем T 3 : натолкнувшись на первую же единицу, она останавливается и вообще ничего не меняет!
Надо заметить, что наш перечень содержит избыточную информацию. Машина T 12 идентична T 6 , а по действиям обе они аналогичны T 0 , поскольку ни T 6 , ни T 12 никогда не переходят во внутреннее состояние 1. Но нам нет нужды волноваться из-за этой избыточности, равно как из-за изобилия неработоспособных (фиктивных) машин Тьюринга в нашем списке. На самом деле, мы могли бы изменить систему кодирования таким образом, чтобы избавиться от большого числа бесполезных устройств и значительно уменьшить избыточность списка машин. Но все это можно сделать только ценой усложнения нашей примитивной универсальной машины Тьюринга, которая должна расшифровывать вводимую в нее запись и имитировать машину T n , чей номер она считала. Это было бы оправдано, если бы было можно избавиться от всех бесполезных (и повторяющихся) машин. Но это, как мы увидим чуть позднее, невозможно! Поэтому мы оставим нашу систему кодирования без изменений.
Будет удобно интерпретировать ленту с последовательностью меток на ней, например
…0001101110010000…,
как двоичное представление некоторого числа. Вспомним, что нули простираются бесконечно в обе стороны, а вот количество единиц конечно. Кроме того, я буду полагать, что их число отлично от нуля(т. е. что в этой последовательности существует хотя бы одна единица). Мы можем тогда считывать конечную строку символов между первой и последней единицами (включительно), которая в предыдущем случае имеет вид
110111001,
как двоичное представление натурального числа (в десятичной форме это 441). Однако такая процедура даст нам только нечетные числа (их двоичное представление оканчивается на 1), тогда как нам нужна возможность представления всех натуральных чисел. Поэтому мы воспользуемся следующим несложным приемом – будем удалять последнюю единицу (которая принимается просто за маркер, обозначающий конец выражения) и считывать оставшуюся часть как двоичное число [46]46
Эта процедура имеет отношение только к методу, который позволяет интерпретировать запись на ленте как натуральное число. Она не изменяет номера наших конкретных машин Тьюринга, таких как EUCи XN + 1.
[Закрыть]. Тогда в последнем примере получим двоичное число
11011100,
которое соответствует десятичному числу 220. Эта процедура имеет то преимущество, что нуль также представляется непустой лентой, а именно:
… 0000001000000….
Рассмотрим, как действует машина Тьюринга T n на некоторую (конечную) строку нулей и единиц на ленте, которая подается в устройство справа. Удобно рассматривать эту строку как двоичное представление некоторого числа, например m , в соответствии с приведенной выше схемой. Предположим, что после определенного числа шагов машина T n в конце концов останавливается (т. е. доходит до команды STOP). Строка двоичных цифр, которые машина выписала к этому моменту на левой части ленты, и будет искомым результатом вычислений. Считывая эту последовательность в соответствии с той же схемой так же как двоичное представление некоторого числа, получим новое число, скажем, р . Тогда мы можем записать соотношение, выражающее тот факт, что результатом действия n-ймашины Тьюринга T n на число m является число p , следующим образом:
T n (m)=p .
Взглянем на это соотношение с несколько иной точки зрения. Мы будем считать, что это выражение описывает некоторую специфическую операцию, которая применяется к паре чисел m и n для того, чтобы получить p . (Это означает: для заданных двух чисел n и m мы можем найти значение p , если введем m в n -ю машину Тьюринга.) Эта специфическая операция является полностью алгоритмической. Поэтому она может быть выполнена одной конкретноймашиной Тьюринга U; иными словами, U, совершая действие над парой (n , m ), дает в результате p . Поскольку машина Uдолжна производить операцию над обоими числами n и m , чтобы получить ответ, выражаемый одним числом p , то нам нужно придумать способ для записи пары (n, m) на однойленте. С этой целью предположим, что n записывается в стандартной двоичной форме и заканчивается последовательностью 111110. (Вспомним, что двоичный номер всякой корректно определенной машины Тьюринга, – это последовательность символов, состоящая только из сочетаний вида 0, 10, 110, 1110 и 11110, поэтому он нигде не содержит более четырех единиц подряд. Таким образом, если T n – корректно определенная машина, то появление последовательности 111110 действительно будет означать конец записи номера n .) Все, что следует за ней, должно быть просто записью числа m на ленте в соответствии с приведенными выше правилами (т. е. двоичное число m и строка 1000… непосредственно за ним). Таким образом, с этой второй частью ленты машина T n и должна производить предполагаемые действия.
Если в качестве примера мы возьмем n =11 и m =6, то на ленте, вводимой в мащину U, мы будем иметь последовательность
000101111111011010000..
Она образована из следующих составляющих:
… 0000 (пустое начало ленты)
1011 (двоичное представление одиннадцати)
111110 (обозначает окончание числа n )
110 (двоичное представление шести)
10000… (остаток ленты)
То, что машина Тьюринга Uдолжна была бы делать на каждом очередном шагу процедуры, выполняемой T n над m – это исследовать структуру последовательности цифр в выражении n с тем, чтобы можно было произвести соответствующие изменения цифр числа m (т. е. «ленты» машины T n ). В принципе, реализация такой машины не вызывает существенных затруднений (хотя и довольно громоздка на практике). Список ее собственных команд должен был бы просто содержать правила для чтения подходящей команды из «списка», закодированного в числе n , на каждом этапе выполнения действий над цифрами, считанными с «ленты», как они фигурируют в числе m . Можно предположить, что при этом совершалось бы значительное количество прыжков взад-вперед по ленте между цифрами, составляющими n и m , и выполнение процедуры было бы чрезвычайно медленным. Тем не менее, список команд подобной машины, несомненно, можно составить, и такая машина называется нами универсальной машиной Тьюринга. Обозначая ее действие на пару чисел (n, m ) через U( n , m ), мы получаем:
U( n , m ) = Т n ( m )
при любых ( n , m ), для которых T n – корректно определенная машина Тьюринга [47]47
Если T n определена некорректно, то Uбудет действовать так, как если бы число, отвечающее n , обрывалось сразу по достижении последовательности из четырех или более единиц в двоичной записи n . Остаток выражения будет считан уже как число m , после чего устройство начнет совершать некие бессмысленные вычисления! От этого свойства можно при желании избавиться, если представлять n в расширеннойдвоичной форме. Я решил не делать этого, чтобы еще больше не усложнять описание несчастной универсальной машины Тьюринга!
[Закрыть]. Машина U, в которую первым вводится число n , в точности имитирует n -ю машину Тьюринга!
Поскольку U– машина Тьюринга, то она сама будет иметь номер. То есть, для некоторого числа u имеем
U = T u .
Сколь велико u ? В сущности, мы можем положить, что u в точности равно следующему числу:
u =7244855335339317577
198395039615711237
952360672556559631
108144796606505059
404241090310483613
632359365644443458
382226883278767626
556144692814117715
017842551707554085
657689753346356942
478488597046934725
739988582283827795
294683460521061169
835945938791885546
326440925525505820
555989451890716537
414896033096753020
431553625034984529
832320651583047664
142130708819329717
234151056980262734
686429921838172157
333482823073453713
421475059740345184
372359593090640024
321077342178851492
760797597634415123
079586396354492269
159479654614711345
700145048167337562
172573464522731054
482980784965126988
788964569760906634
204477989021914437
932830019493570963
921703904833270882
596201301773727202
718625919914428275
437422351355675134
084222299889374410
534305471044368695
876405178128019437
530813870639942772
823156425289237514
565443899052780793
241144826142357286
193118332610656122
755531810207511085
337633806031082361
675045635852164214
869542347187426437
544428790062485827
091240422076538754
264454133451748566
291574299909502623
009733738137724162
172747723610206786
854002893566085696
822620141982486216
989026091309402985
706001743006700868
967590344734174127
874255812015493663
938996905817738591
654055356704092821
332221631410978710
814599786695997045
096818419062994436
560151454904880922
084480034822492077
304030431884298993
931352668823496621
019471619107014619
685231928474820344
958977095535611070
275817487333272966
789987984732840981
907648512726310017
401667873634776058
572450369644348979
920344899974556624
029374876688397514
044516657077500605
138839916688140725
455446652220507242
623923792115253181
625125363050931728
631422004064571305
275802307665183351
995689139748137504
926429605010013651
980186945639498
(или какому-нибудь другому подходящему, не менее внушительному по величине числу). Это число, без сомнения, выглядит устрашающе большим! Оно, действительно, чрезвычайно велико, но я не вижу способа, как его можно было бы сделать меньше. Процедуры кодирования и определения, использованные мною для машин Тьюринга, вполне разумны и достаточно просты, и все же с неизбежностью приводят к подобным несуразно большим числам для реальной универсальной машины Тьюринга [48]48
Я благодарен Давиду Дойчу за то, что он нашел десятичную форму двоичного представления u , которое я привожу ниже. Я признателен ему также за проверку того факта, что это двоичное значение и действительнозадает универсальную машину Тьюринга! Двоичная запись и выглядит следующим образом:
10000000010111010011010
00100101010110100011010
00101000001101010011010
00101010010110100001101
00010100101011010010011
10100101001001011101010
00111010101001001010111
01010100110100010100010
10110100000110100100000
10101101000100111010010
10000101011101001000111
01001010100001011101001
01001101000010000111010
10000111010100001001001
11010001010101101010010
10110100000110101010010
11010010010001101000000
00110100000011101010010
10101011101000010011101
00101010101010101110100
00101010111010000101000
10111010001010011010010
00010100110100101001001
10100100010110101000101
11010010010101110100101
00011101010010100100111
01010101000011010010101
01011101010010001011010
10000101101010001001101
01010101000101101001010
10010010110101001001011
10101010010101110101001
01001101010100001110100
01001001010111010101001
01011101010100000111010
10010000011010101010010
11101010010101101000100
10001110100000001110100
10100101010101110100101
00100101011101000001010
11101000010001110100000
10101001110100001010011
10100000100010111010001
00001110100001001010011
10100010000101101000101
00101110100010100101101
00100000101101000101010
01001101000101010101110
10010000011101001001010
10101110101010100110100
10001010110100100100101
10100000001011010000010
00110100000100101101000
00000011010010100010111
01001010100011010010100
10101101000001001110100
10101001011010010011101
01000000101011101010000
00110101010001010101101
00101010110101000010101
11010100100101011101010
00100101101010010000101
11010000001110101001000
10110101001010011010101
00010111010100101001011
10101010000010111010101
00000101110100000011101
01010000101011101001010
10110101010000101110101
00010101011101010100100
10111010101010000111010
10000000111010010010000
11010010010001011010101
01010011101000000001011
01001000011010101010100
10111010010000110100100
01010101110100001000111
01000100001110100001101
00000001011010000010010
11101010100101010110100
01000100101110100000100
11101010100110100000101
01011010000100001110100
10000100011101010101010
10011101000010010011101
00010010000111010000101
00101101000010100001110
10101010101011101000100
10011010001001001101010
01010010111010001000101
01110100000001110100010
01001011101001101001001
00001011010101010011010
00101000101110100001101
01000010001011010100110
10101001010010110101010
01101001001010111010011
01001000001011010001010
10100011101001000010101
10100000010011010010001
00101110100100001101010
00001001011101001001010
01101001001010101101001
10100100101001011010011
01001010000010110100100
00011101010010011010101
01000010111010010100001
01110100101010101110101
00010010110100100111010
01010100010111010001001
11010100001011010010011
10100101010101011101001
00011101001010101001011
10100100011101010000010
10101110011010100000101
10100100111010100000010
11101001011010100000101
01101001010010111010100
00100101110100001101010
00100001011010100110101
00010001011010101010010
11101010001010010110100
01010101011101001000010
10110101000101110101001
00101010111010101001001
01110101000111010100011
10101001001001011101010
00111010100101000101110
10100010111010100001001
01110101000111010001010
00101110100101001011101
01001010100101110100101
01010101011010100001010
10101101000010011101000
01010101010111010101000
10101110101010001010111
01000000111010101000100
10111010000001110101010
01000101110101000000110
10100001011010000001110
10010000001011101010001
11010100100010101110101
00110101010100010101101
00000110101010100101010
11010000001001101010101
00100111010100110101010
10010010110101001101001
00100111010000011010101
01010010101101010001001
10100010100101010111010
00001101010101010100101
10100010001110100010101
01010101101000100011101
00001010111010001001000
01110100110100000001001
11010000001001011101000
10001010011101000000100
10111010010101010100101
10100001010101011101000
10010100101110100000100
01011101010100101101000
10001001110100000100101
01110100000010101011010
00010001110011110100001
00000111010000100100111
01000001010010111010000
01010010110100001000101
01110100001000100110100
01000011101011110100001
00100101110100001001001
01110100000001010111010
00010101000110100010010
11101000010000011101000
01001110100010000010111
01010100101101000100000
10111010000101010101110
10000001010101110100010
00010101110100010000101
01110100100000111010100
10010011010000001010111
01000100010010111010101
00001110101001010110100
10101010000110100000101
00110100000001110100000
10010011101001011010010
00101001011010101001101
00010100100101101010100
11010001010100010110011
01010010010111010101001
10100010101010101100110
10100010101011001101001
00010101010111010001000
11101001001010101010110
10010100101000110100100
00001011101000001101010
10010101010110100101010
11010010001000101110100
01010101101010000010101
10100010000011010010001
01011010000100111010100
10101010101110100101101
00100100010101100110100
10010010101011101001101
00100100101011010010110
10010010010010110100101
10100100101000101100110
10010010100101011101000
10101110100100101110011
01001001010100101110011
01001010001010101110100
01000111010000101001011
01001010001011101001010
00101011010001001110100
10100010010111010001001
11010010100100010111001
10100100010001110100010
01110100101001010101110
01101001010000011100110
10101010101101000000011
10100101010010101011101
00100011101001010100101
01110011010000101001001
10011010100000110100000
00111010010101010010101
11001101010001000011010
00000011101000100101010
10111010001000111010101
01010101010110100001001
11010010001001010111010
01010100010011010100000
00101101001001110101000
01010111010010000110101
00000001011010010001110
10100100101110100001101
01000010101011010100010
11101010000101001011101
01000101110101000101010
10111001101010001010110
100001101010001001010
Пытливый читатель, вооруженный эффективным домашним компьютером, быть может захочет проверить, используя данные в тексте предписания и применяя эту последовательность к номерам различных простых машин Тьюринга, что она и в самом деле соответствует универсальной машине Тьюринга! Некоторое уменьшение величины и может быть достигнуто за счет другого определения машины Тьюринга. Например, мы могли бы отказаться от использования команды STOPи вместо этого применять правило остановки после того, как машина повторно возвращается во внутреннее состояние 0 из какого-либо другого внутреннего состояния. Это не дало бы нам значительного выигрыша (а может, и вовсе никакого). Большую пользу принесло бы использование лент с иными, нежели только 0и 1, отметками. В литературе встречаются описания очень компактных на вид машин Тьюринга, но эта компактность обманчива, поскольку она обусловлена чрезмерно сложным кодированием описаний машин Тьюринга вообще.
[Закрыть].
Я уже говорил, что все современные общеупотребительные компьютеры, по сути, являются универсальными машинами Тьюринга. Я ни в коем случае не подразумеваю под этим, что их логическая структура должна в точности походить на предложенную мной выше структуру универсальной машины Тьюринга. Однако суть дела состоит в том, что если сперва ввести в произвольную универсальную машину Тьюринга соответствующую программу (начало подаваемой на вход ленты), то потом она сможет копировать поведение любой машины Тьюринга! В предыдущем примере программа просто принимает форму одного числа (числа n ), но этим разнообразие возможных процедур и вариантов исходной схемы Тьюринга отнюдь не исчерпывается. В действительности я сам, описывая машину, несколько отклонился от того, что исходно было предложено Тьюрингом. Но ни одно из этих отклонений не имеет сейчас для нас существенного значения.
Неразрешимость проблемы Гильберта
Мы теперь вплотную подходим к той цели, ради которой Тьюринг с самого начала разрабатывал свою теорию – получить ответ на вопрос, заключенный в общей проблеме алгоритмической разрешимости, поставленной Гильбертом, а именно: существует ли некая механическая процедура для решения всех математических задач, принадлежащих к некоторому широкому, но вполне определенному классу? Тьюринг обнаружил, что он мог бы перефразировать этот вопрос следующим образом: остановится лив действительности n-я машина Тьюринга, если на ее вход поступит число m Эта задача получила название проблемы остановки . Не так сложно составить список команд, для которых машина никогда не остановится при любом m (как, например, в случаях n = 1 или 2, рассмотренных в предыдущем разделе, а также во всех случаях, когда вообще отсутствует команда STOP). Точно так же существует множество списков команд, для которых машина будет останавливаться всегда, независимо от вводимого числа m (например, T 11 ). Кроме того, некоторые машины при работе с одними числами останавливались бы, а с другими – нет. Совершенно очевидно, что алгоритм, который никогда не прекращает работу, бесполезен. Это, собственно, и не алгоритм вовсе. Поэтому важно уметь ответить на вопрос, приведет ли когда-нибудь работа машины T n над данным числом m к какому-то ответу или нет! Если нет (т. е. процесс вычисления никогда не прекращается), то я буду выражать это следующей записью:
T n (m ) = □.
(Сюда же включены машины, которые в ходе работы попадают в ситуацию, когда нет команды, определяющей их дальнейшее поведение, как это было в случае рассмотренных выше фиктивных машин T 4 и T 1 . К сожалению, наша на первый взгляд работоспособная машина T 3 должна теперь также считаться фиктивной, т. е.
T 3 (m ) = □, поскольку результатом ее действия всегда будет просто пустая лента, тогда как нам, чтобы приписать номер полученному ответу, нужна хотя бы одна единица на выходе! Машина T 11 , однако, совершенно полноправна, поскольку она производит единственную 1. Результатом ее работы будет лента с номером 0, так что T 11 ( m ) = 0 для любого m .)
В математике весьма важно иметь возможность установить момент, когда машина Тьюринга остановится. Рассмотрим для примера уравнение
( х+ 1) ω+3+ ( у+ 1) ω+3= ( z+ 1) ω+3.
(Не пугайтесь, даже если Вы не любите вникать в детали математических вычислений. Это уравнение используется здесь только в качестве примера, и от вас не требуется его глубокого понимания.) Это конкретное уравнение относится к известной (возможно, самой известной) и пока нерешенной математической проблеме. Проблема формулируется следующим образом: существует ли какой-либо набор х , у , z , ω , для которого это равенство выполняется. Знаменитое утверждение, записанное на полях «Арифметики» Диофанта великим французским математиком семнадцатого столетия Пьером де Ферма (1601–1665) и известное как «последняя теорема Ферма», гласит, что это равенство никогда не выполняется [49]49
Напомним, что натуральнымимы называем числа 0,1,2,3,4,5,6… Вместо обычной записи ( x ω+ y ω= z ω, где х, у, z> 0, ω> 2) мы используем «х + 1», « ω+ 3» и т. д., чтобы включить в рассмотрение все натуральные числа, начиная с нуля.
[Закрыть] [50]50
Желающие ознакомиться с вопросами, имеющими отношение к этому знаменитому утверждению и изложенными без излишних технических подробностей, могут обратиться к работе Дэвлина [1988].
[Закрыть]. Будучи адвокатом по профессии, Ферма тем не менее был искуснейшим математиком своего времени. (Ферма был современником Декарта.) В своей записи он утверждал, что знает «воистину прекрасное доказательство» своей теоремы, но поля книги слишком малы, чтобы его привести. До сегодняшнего дня никому так и не удалось ни воспроизвести это доказательство [51]51
Последняя теорема Ферма доказана английским математиком Эндрю Уайлсом (Andrew J. Wiles). Доказательство опубликовано в 1995 году. – Прим. ред.
[Закрыть], ни найти опровергающий это утверждение пример!
Очевидно, что для заданнойчетверки чисел ( x, у, z, ω ) выяснить, выполняется это равенство или нет, можно простым вычислением. Значит, мы можем представить себе вычислительный алгоритм, который последовательно перебирает все возможные четверки чисел одну за другой и останавливается только тогда, когда равенство удовлетворяется. (Мы уже знаем, что для конечных наборов чисел существуют способы их кодирования на ленте вычислимым способом, а именно, в виде одного числа. Таким образом, перебор всех четверок можно провести, просто следуя естественному порядку соответствующих им одиночных чисел.) Если бы мы могли установить, что этот алгоритм никогда не останавливается, то это стало бы доказательством утверждения Ферма.
Сходным образом в терминах проблемы остановки машины Тьюринга можно перефразировать многие другие нерешенные математические проблемы. Примером такого рода проблем может служить так называемое предположение Гольдбаха: любое четное число, большее двух, может быть представлено в виде суммы двух простых чисел [52]52
Напомним, что простые числа 2, 3, 5, 7, 11, 13, 17… – это такие натуральные числа, которые делятся только на самих себя и на единицу. Ни нуль, ни единица простыми числами не считаются.
[Закрыть]). Процесс, с помощью которого можно установить, относится некоторое натуральное число к простым или нет, является алгоритмическим, поскольку достаточно проверить делимость данного числа на все числа, меньшиеего, а это достигается с помощью конечногочисла вычислительных операций. Мы можем придумать машину Тьюринга, которая перебирает четные числа 6, 8, 10, 12, 14…, пробуя все возможные способы разбиения их на пары нечетных чисел
6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7 = 5 +5,
12 = 5 + 7, 14 = 3 + 11=7 + 7…
и убеждаясь, что для каждогочетного числа какое-тоиз разбиений образовано двумя простыми числами. (Очевидно, нам не надо проверять пары четных слагаемых, кроме 2 + 2, поскольку все простые числа за исключением 2 – нечетные.) Наша машина должна остановиться только в том случае, если она находит четное число, для которого ни одноиз разбиений не является парой простых чисел. В этом случае мы получили бы контрпример к предположению Гольдбаха, т. е. нашли бы четное число, большее 2, которое не является суммой двух простых чисел. Следовательно, если бы мы могли установить, останавливается машина Тьюринга когда-нибудь или нет, то тем самым мы выяснили бы, справедливо предположение Гольдбаха или нет.
Возникает естественный вопрос: каким образом следует определять, остановится какая-то определенная машина Тьюринга (в которую введены конкретные начальные данные) или нет? Для многих машин Тьюринга ответить на этот вопрос нетрудно, но, как мы видели выше, иногда для ответа может потребоваться решение какой-нибудь до сих пор не решенной математической задачи. Так существует ли некая алгоритмическаяпроцедура для решения общей проблемы – проблемы остановки – полностью механическим путем? Тьюринг показал, что такой процедуры на самом деле нет.
В сущности, его доказательство сводилось к следующему. Предположим, наоборот, что указанный алгоритм существует [53]53
Это хорошо известный и очень мощный метод математического доказательства, называемый «доказательством от противного» или reductio ad absurdum(сведение к абсурду), в котором сначала полагается истинным утверждение, исключающее исходное, затем из этой предпосылки выводится противоречие, которое и служит доказательством справедливости исходного утверждения.
[Закрыть]. Тогда существует и некая машина Тьюринга Н, которая «решает», остановится ли в конце концов n -я машина Тьюринга, действуя на число m . Условимся, что результатом действия машины Нбудет лента с номером 0, если n -я машина не останавливается, и с номером 1в противоположном случае:
Здесь мы могли бы воспользоваться способом кодирования пары ( n , m ), использованным ранее для универсальной машины Тьюринга U. Однако это привело бы к проблеме технического характера, поскольку при некоторых n (например, n = 7) T n будет определена некорректно, и маркер 111101будет непригоден для отделения на ленте n от m . Чтобы избежать этой проблемы, будем полагать, что n представлено не в двоичной, а в расширеннойдвоичной форме, тогда как для m будет по-прежнему использоваться обычная двоичная запись. В этом случае комбинации 110будет достаточно для разделения n и m . Использование точки с запятой в обозначении Н( n ; m ) в отличие от запятой в обозначении универсальной машины U( n , m ) указывает на это различие в кодировании.
Представим себе теперь бесконечную таблицу, в которую включены окончательные результаты действий всех возможных машин Тьюринга на все возможные (различные) входные данные. В этой таблице N-й ряд представляет собой результаты вычислений n-й машины Тьюринга, полученные при ее работе последовательно с m = 0, 1, 2, 3, 4…:
Я немного «сжульничал» и не стал располагать машины Тьюринга по порядку их действительныхномеров. Если бы я так сделал, то получился бы список, начало которого выглядело бы слишком скучным, поскольку все машины при значениях n меньших 11 не дают ничего, кроме □, а для n = 11 мы имеем просто нули. Дабы сделать начало этой таблицы более интересным, я предположил, что мы использовали некую гораздо более эффективную систему кодирования. Фактически, я просто присвоил ячейкам более или менее произвольные значения, только чтобы дать вам общее представление о том, как может выглядеть эта таблица.
На самом деле нам не требуется, чтобы эта таблица была построена путем вычислений, скажем, с помощью некоторого алгоритма. (На самом деле, как мы увидим далее, такого алгоритма и не существует.) Достаточно просто представитьсебе, что каким-то образом истинныйсписок попал в наше распоряжение, возможно, с помощью Бога! Если бы мы попытались получить эту таблицу с помощью вычислений, то именно символы □вызвали бы затруднения, поскольку мы не могли бы с уверенностью сказать, когда в той или иной ячейке должен быть помещен символ □– ведь соответствующие вычисления никогда не заканчиваются!
Тем не менее искомую таблицу можно, построить с помощью вычислительной процедуры, если использовать нашу гипотетическую машину Н, поскольку она могла бы определить, где на самом деле появляются значения □. Однако вместо этого мы используем машину Ндля того, чтобы избавитьсяот появления значений □в таблице, заменив их во всех случаях нулями. Это достигается за счет вычисления значения Н( n ; m ), предваряющего действие T n на m , после чего мы позволим T n производить соответствующие действия, только если H( n ; m ) = 1 (т. е. только тогда, когда вычисление T n (m) приводит к определенному результату), и будем просто записывать в соответствующую ячейку 0при Н( n ; m ) = 0 (т. е. если T n ( m ) = □). Мы можем записать эту новую процедуру, представляющую собой последовательное действие Н( n ; m ) и T(m), как
T n (m) х Н( n; m ).
(Здесь я использую общепринятую в математике договоренность о последовательности выполнения действий, согласно которой операция, записанная справа, должна выполняться первой. Обратите внимание, что в этом случае можно символически записать □х 0 = 0.)
Теперь таблица принимает следующий вид:
Заметьте, что, исходя из предположения существования машины Н, мы получаем ряды таблицы, состоящие из вычислимыхпоследовательностей. (Под «вычислимой последовательностью» я понимаю бесконечную последовательность, элементы могут быть найдены один за другим посредством некоего алгоритма; это означает, что существует некоторая машина Тьюринга, которая, будучи применена поочередно к натуральным числам m = 0, 1, 2, 3, 4, 5…, производит члены рассматриваемой последовательности.) Обратите внимание на следующие два факта относительно этой таблицы. Во-первых, любаявычислимая последовательность натуральных чисел должна появиться где-то (может быть, далеко не сразу) среди рядов таблицы. Это свойство выполнялось уже и для исходной таблицы, содержавшей значения □. Мы просто добавилинесколько рядов, чтобы заменить «фиктивные» машины Тьюринга (т. е. такие, которые приводят к □хотя бы в одном случае). Во-вторых, считая, что машина Тьюринга Hсуществует, мы получили таблицу вычислительным путем(т. е. с помощью некоторого определенного алгоритма), а именно, посредством процедуры T n (m) х Н( n ; m ). Иными словами, существует некая машина Тьюринга Q, применение которой к паре чисел ( n , m ) дает значение соответствующей ячейки таблицы. Для этой машины числа n и m на ленте можно кодировать таким же образом, как и для H, т. е. мы имеем
Q( n ; m ) = T n ( m ) х H ( n ; m ).
Воспользуемся теперь разновидностью остроумного и мощного приема, так называемого диагонального процессаГеорга Кантора. (Мы познакомимся с оригинальным вариантом этого метода в следующей главе.) Рассмотрим значения в ячейках, расположенных на главной диагонали таблицы – диагональные элементы (матрицы), – выделенные жирным шрифтом:
Эти элементы образуют некоторую последовательность 0,0,1,2,1,0, 3,7,1…., к каждому члену которой мы теперь прибавим единицу:
1, 1, 2, 3, 2, 1, 4, 8, 2…
Это, безусловно, механическая процедура, и, поскольку наша таблица была получена путем вычислений, мы получим новую вычислимую последовательность 1 + Q( n ; m ), т. е.
1 + T n ( n ) х H ( n ; n )
(с учетом того, что для диагональных элементов n = m ). Но наша таблица содержит в себе все вычислимые последовательности, поэтому она должна содержать также и новую последовательность. Однако это невозможно! Ведь наша новая последовательность отличается от первого ряда первым элементом, от второго – вторым, от третьего – третьим, и т. д. Налицо явное противоречие, которое и устанавливает справедливость доказываемого нами утверждения о том, что машина Тьюринга Hна самом деле не существует! Иными словами, не существует универсального алгоритма для решения вопроса об остановке произвольной машины Тьюринга.
Можно построить доказательство и по-другому. Для этого заметим, что из предположения о существовании Hследует и существование машины Тьюринга с номером k , реализующей алгоритм (диагональный процесс!) 1 + Q( n ; n ), т. е. можно записать
