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

Числа, отличные от натуральных

В предыдущих параграфах мы рассматривали действия над натуральнымичислами и отметили тот замечательный факт, что машина Тьюринга может оперировать с натуральными числами произвольной величины, несмотря на то, что каждая машина имеет фиксированное и конечноечисло внутренних состояний. Однако часто возникает необходимость в операциях с более сложными числами, такими как отрицательные числа, обыкновенные дроби и бесконечные десятичные дроби. Первые две категории (т. е. числа вида – 597/26) легко поддаются обработке машинами Тьюринга, причем и числители, и знаменатели могут быть сколь угодно большими. Все, что для этого нужно — какой-нибудь подходящий код для знаков «-»и « /», который можно легко выбрать при использовании расширенной двоичной записи (например, « 3» = 1110для знака «-», а « 4»= 11110— для знака « /»). Таким образом, отрицательные числа и обыкновенные дроби рассматриваются как конечные наборы натуральных чисел, и с точки зрения общих вопросов вычислимости ничего нового не дают.

То же можно сказать и о конечныхдесятичных выражениях с произвольным числом знаков после запятой, поскольку они представляют собой лишь частный случай обыкновенных дробей. Так, например, конечная десятичная аппроксимация иррационального числа , заданная числом 3,14159265, есть просто дробь 314 159 265/100 000 000. Однако бесконечныедесятичные выражения, такие как полная запись числа

= 3,14159265358979…,

представляют определенные трудности. На самом деле, ни входные, ни выходные данные машины Тьюринга не могут быть бесконечными десятичными выражениями. Можно было бы думать, что нашлась бы машина Тьюринга, способная выдавать одну за другой все последовательные цифры — 3, 1, 4, 1, 5, 9… в десятичной записи числа и переносить их на выходную ленту, а мы просто позволим этой машине работать бесконечно долго. Но это запрещенодля машин Тьюринга. Мы должны дождаться остановки машины (сопровождаемой звонком колокольчика!), прежде чем сможем ознакомиться с результатом. До того момента, пока машина не выполнит команды STOP, выходные данные могут изменяться и поэтому не являются достоверными. С другой стороны, после полной остановки машины результат должен быть с необходимостью конечным.

Существует, однако, «законная» процедура для того, чтобы заставить машину Тьюринга последовательно воспроизводить цифры примерно так, как это предлагалось выше. Если мы хотим получить бесконечную десятичную запись, скажем, числа , мы могли бы заставить машину Тьюринга сначала рассчитать его целую часть, 3, используя на входе 0, затем — первую цифру дробной части, 1, используя на входе 1, затем — вторую цифру дробной части, 4, используя на входе 2, потом — третью цифру, 1, используя 3 и т. д. Вообще говоря, машина Тьюринга для получения всех цифр десятичной записи числа в этом смысле действительно существует, хотя реализовать ее в явном виде было бы затруднительно. Подобное же замечание относится и ко многим другим иррациональным числам, таким, например, как 2 = 1,414213562… Однако оказывается — и мы увидим это в следующей главе, — что некоторые иррациональные числа принципиально не могут быть получены с помощью машины Тьюринга. Числа, которые можнополучить таким образом, называются вычислимыми(Тьюринг [1937]), а остальные (в действительности абсолютное большинство!) — невычислимыми. Я еще вернусь к этой теме и затрону ряд смежных вопросов в последующих главах. К нам это имеет отношение в связи с вопросом о том, может ли реальный физический объект (например, человеческий мозг) быть адекватно описан в терминах вычислимых математических структур в соответствии с нашими физическими теориями.

Проблема вычислимости важна для математики в целом. Не следует думать, что она относится только к числамкак таковым. Ведь машины Тьюринга могут непосредственно оперировать математическими формулами, например, алгебраическими или тригонометрическими выражениями, или выполнять формальные действия математического анализа. Все, что для этого нужно, это некий способ точного кодирования всех используемых математических символов в виде последовательностей нулей и единиц, которые позволят применить соответствующую машину Тьюринга. Именно это Тьюринг имел в виду, когда он взялся за проблему алгоритмической разрешимости, в которой требуется найти алгоритмическую процедуру для ответа на самые общие математические вопросы. Очень скоро мы вновь обратимся к этой теме.

Универсальная машина Тьюринга

Я еще не затрагивал понятия универсальноймашины Тьюринга. Лежащий в ее основе принцип понять нетрудно, хотя детали могут быть сложны. Основная идея состоит в том, чтобы закодировать команды для произвольной машины Тьюринга Тв виде последовательности нулей и единиц, которую можно записать на ленте. Эта запись используется как начальная часть входных данных для некоторой особоймашины Тьюринга 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с двоичным номером