Роджер Пенроуз - Новый ум короля: О компьютерах, мышлении и законах физики
000101111111011010000..
Она образована из следующих составляющих:
… 0000 (пустое начало ленты)
1011 (двоичное представление одиннадцати)
111110 (обозначает окончание числа n )
110 (двоичное представление шести)
10000… (остаток ленты)
То, что машина Тьюринга U должна была бы делать на каждом очередном шагу процедуры, выполняемой Tn над m — это исследовать структуру последовательности цифр в выражении n с тем, чтобы можно было произвести соответствующие изменения цифр числа m (т. е. «ленты» машины Tn ). В принципе, реализация такой машины не вызывает существенных затруднений (хотя и довольно громоздка на практике). Список ее собственных команд должен был бы просто содержать правила для чтения подходящей команды из «списка», закодированного в числе n, на каждом этапе выполнения действий над цифрами, считанными с «ленты», как они фигурируют в числе m. Можно предположить, что при этом совершалось бы значительное количество прыжков взад-вперед по ленте между цифрами, составляющими n и m, и выполнение процедуры было бы чрезвычайно медленным. Тем не менее, список команд подобной машины, несомненно, можно составить, и такая машина называется нами универсальной машиной Тьюринга. Обозначая ее действие на пару чисел (n, m ) через U(n, m ), мы получаем:
U(n, m ) = Тn(m )
при любых (n, m ), для которых Tn — корректно определенная машина Тьюринга[47]. Машина U, в которую первым вводится число n, в точности имитирует n-ю машину Тьюринга!
Поскольку U — машина Тьюринга, то она сама будет иметь номер. То есть, для некоторого числа u имеем
U = Tu.
Сколь велико 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].
Я уже говорил, что все современные общеупотребительные компьютеры, по сути, являются универсальными машинами Тьюринга. Я ни в коем случае не подразумеваю под этим, что их логическая структура должна в точности походить на предложенную мной выше структуру универсальной машины Тьюринга. Однако суть дела состоит в том, что если сперва ввести в произвольную универсальную машину Тьюринга соответствующую программу (начало подаваемой на вход ленты), то потом она сможет копировать поведение любой машины Тьюринга! В предыдущем примере программа просто принимает форму одного числа (числа n ), но этим разнообразие возможных процедур и вариантов исходной схемы Тьюринга отнюдь не исчерпывается. В действительности я сам, описывая машину, несколько отклонился от того, что исходно было предложено Тьюрингом. Но ни одно из этих отклонений не имеет сейчас для нас существенного значения.
Неразрешимость проблемы Гильберта
Мы теперь вплотную подходим к той цели, ради которой Тьюринг с самого начала разрабатывал свою теорию — получить ответ на вопрос, заключенный в общей проблеме алгоритмической разрешимости, поставленной Гильбертом, а именно: существует ли некая механическая процедура для решения всех математических задач, принадлежащих к некоторому широкому, но вполне определенному классу? Тьюринг обнаружил, что он мог бы перефразировать этот вопрос следующим образом: остановится ли в действительности n-я машина Тьюринга, если на ее вход поступит число m Эта задача получила название проблемы остановки. Не так сложно составить список команд, для которых машина никогда не остановится при любом m (как, например, в случаях n = 1 или 2, рассмотренных в предыдущем разделе, а также во всех случаях, когда вообще отсутствует команда STOP ). Точно так же существует множество списков команд, для которых машина будет останавливаться всегда, независимо от вводимого числа m (например, T11 ). Кроме того, некоторые машины при работе с одними числами останавливались бы, а с другими — нет. Совершенно очевидно, что алгоритм, который никогда не прекращает работу, бесполезен. Это, собственно, и не алгоритм вовсе. Поэтому важно уметь ответить на вопрос, приведет ли когда-нибудь работа машины Tn над данным числом m к какому-то ответу или нет! Если нет (т. е. процесс вычисления никогда не прекращается), то я буду выражать это следующей записью:
Tn(m ) = □.
(Сюда же включены машины, которые в ходе работы попадают в ситуацию, когда нет команды, определяющей их дальнейшее поведение, как это было в случае рассмотренных выше фиктивных машин T4 и T1. К сожалению, наша на первый взгляд работоспособная машина T3 должна теперь также считаться фиктивной, т. е.
T3(m ) = □, поскольку результатом ее действия всегда будет просто пустая лента, тогда как нам, чтобы приписать номер полученному ответу, нужна хотя бы одна единица на выходе! Машина T11, однако, совершенно полноправна, поскольку она производит единственную 1. Результатом ее работы будет лента с номером 0, так что T11(m ) = 0 для любого m.)
В математике весьма важно иметь возможность установить момент, когда машина Тьюринга остановится. Рассмотрим для примера уравнение
(х + 1)ω+3 + (у + 1)ω+3 = (z + 1)ω+3.
(Не пугайтесь, даже если Вы не любите вникать в детали математических вычислений. Это уравнение используется здесь только в качестве примера, и от вас не требуется его глубокого понимания.) Это конкретное уравнение относится к известной (возможно, самой известной) и пока нерешенной математической проблеме. Проблема формулируется следующим образом: существует ли какой-либо набор х, у, z, ω, для которого это равенство выполняется. Знаменитое утверждение, записанное на полях «Арифметики» Диофанта великим французским математиком семнадцатого столетия Пьером де Ферма (1601–1665) и известное как «последняя теорема Ферма», гласит, что это равенство никогда не выполняется[49][50]. Будучи адвокатом по профессии, Ферма тем не менее был искуснейшим математиком своего времени. (Ферма был современником Декарта.) В своей записи он утверждал, что знает «воистину прекрасное доказательство» своей теоремы, но поля книги слишком малы, чтобы его привести. До сегодняшнего дня никому так и не удалось ни воспроизвести это доказательство[51], ни найти опровергающий это утверждение пример!
