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

Пенроуз Роджер

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

T _n (m ) = .

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

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

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

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

(Не пугайтесь, даже если Вы не любите вникать в детали математических вычислений. Это уравнение используется здесь только в качестве примера, и от вас не требуется его глубокого понимания.) Это конкретное уравнение относится к известной (возможно, самой известной) и пока нерешенной математической проблеме. Проблема формулируется следующим образом: существует ли какой-либо набор х , у , z , , для которого это равенство выполняется. Знаменитое утверждение, записанное на полях «Арифметики» Диофанта великим французским математиком семнадцатого столетия Пьером де Ферма (1601–1665) и известное как «последняя теорема Ферма», гласит, что это равенство никогда не выполняется [49] [50] . Будучи адвокатом по профессии, Ферма тем не менее был искуснейшим математиком своего времени. (Ферма был современником Декарта.) В своей записи он утверждал, что знает «воистину прекрасное доказательство» своей теоремы, но поля книги слишком малы, чтобы его привести. До сегодняшнего дня никому так и не удалось ни воспроизвести это доказательство [51] , ни найти опровергающий это утверждение пример!

49

Напомним, что натуральнымимы называем числа 0,1,2,3,4,5,6… Вместо обычной записи ( x + y = z , где х, у, z> 0, > 2) мы используем «х + 1», « + 3» и т. д., чтобы включить в рассмотрение все натуральные числа, начиная с нуля.

50

Желающие ознакомиться с вопросами, имеющими отношение к этому знаменитому утверждению и изложенными без излишних технических подробностей, могут обратиться к работе Дэвлина [1988].

51

Последняя теорема Ферма доказана английским математиком Эндрю Уайлсом (Andrew J. Wiles). Доказательство опубликовано в 1995 году. — Прим. ред.

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

Сходным образом в терминах проблемы остановки машины Тьюринга можно перефразировать многие другие нерешенные математические проблемы. Примером такого рода проблем может служить так называемое предположение Гольдбаха: любое четное число, большее двух, может быть представлено в виде суммы двух простых чисел [52] ). Процесс, с помощью которого можно установить, относится некоторое натуральное число к простым или нет, является алгоритмическим, поскольку достаточно проверить делимость данного числа на все числа, меньшиеего, а это достигается с помощью конечногочисла вычислительных операций. Мы можем придумать машину Тьюринга, которая перебирает четные числа 6, 8, 10, 12, 14…, пробуя все возможные способы разбиения их на пары нечетных чисел

52

Напомним, что простые числа 2, 3, 5, 7, 11, 13, 17… - это такие натуральные числа, которые делятся только на самих себя и на единицу. Ни нуль, ни единица простыми числами не считаются.

6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7 = 5 +5,

12 = 5 + 7, 14 = 3 + 11=7 + 7…

и убеждаясь, что для каждогочетного числа какое-тоиз разбиений образовано двумя простыми числами. (Очевидно, нам не надо проверять пары четных слагаемых, кроме 2 + 2, поскольку все простые числа за исключением 2 — нечетные.) Наша машина должна остановиться только в том случае, если она находит четное число, для которого ни одноиз разбиений не является парой простых чисел. В этом случае мы получили бы контрпример к предположению Гольдбаха, т. е. нашли бы четное число, большее 2, которое не является суммой двух простых чисел. Следовательно, если бы мы могли установить, останавливается машина Тьюринга когда-нибудь или нет, то тем самым мы выяснили бы, справедливо предположение Гольдбаха или нет.