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

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₁₁). Кроме того, некоторые машины при работе с одними числами останавливались бы, а с другими — нет. Совершенно очевидно, что алгоритм, который никогда не прекращает работу, бесполезен. Это, собственно, и не алгоритм вовсе. Поэтому важно уметь ответить на вопрос, приведет ли когда-нибудь работа машины  T_nнад данным числом mк какому-то ответу или нет! Если нет(т. е. процесс вычисления никогда не прекращается), то я буду выражать это следующей записью:

T_n(m)= .

(Сюда же включены машины, которые в ходе работы попадают в ситуацию, когда нет команды, определяющей их дальнейшее поведение, как это было в случае рассмотренных выше фиктивных машин  T₄и T₁. К сожалению, наша на первый взгляд работоспособная машина  T₃должна теперь также считаться фиктивной, т. е.

T₃(m)= , поскольку результатом ее действия всегда будет просто пустая лента, тогда как нам, чтобы приписать номер полученному ответу, нужна хотя бы одна единица на выходе! Машина T₁₁, однако, совершенно полноправна, поскольку она производит единственную 1. Результатом ее работы будет лента с номером 0, так что T₁₁( m) = 0 для любого m.)

В математике весьма важно иметь возможность установить момент, когда машина Тьюринга остановится. Рассмотрим для примера уравнение

( х+ 1) ⁺³+ ( у+ 1) ⁺³= ( z+ 1) ⁺³.