Роджер Пенроуз - Новый ум короля: О компьютерах, мышлении и законах физики

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 (например, 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] [50]. Будучи адвокатом по профессии, Ферма тем не менее был искуснейшим математиком своего времени. (Ферма был современником Декарта.) В своей записи он утверждал, что знает «воистину прекрасное доказательство» своей теоремы, но поля книги слишком малы, чтобы его привести. До сегодняшнего дня никому так и не удалось ни воспроизвести это доказательство [51], ни найти опровергающий это утверждение пример!

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