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

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

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

В предыдущих параграфах мы рассматривали действия над натуральными числами и отметили тот замечательный факт, что машина Тьюринга может оперировать с натуральными числами произвольной величины, несмотря на то, что каждая машина имеет фиксированное и конечное число внутренних состояний. Однако часто возникает необходимость в операциях с более сложными числами, такими как отрицательные числа, обыкновенные дроби и бесконечные десятичные дроби. Первые две категории (т. е. числа вида -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]), а остальные (в действительности абсолютное большинство!) — невычислимыми. Я еще вернусь к этой теме и затрону ряд смежных вопросов в последующих главах. К нам это имеет отношение в связи с вопросом о том, может ли реальный физический объект (например, человеческий мозг) быть адекватно описан в терминах вычислимых математических структур в соответствии с нашими физическими теориями.

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

Оглавление книги