Новый ум короля: О компьютерах, мышлении и законах физики
Шрифт:
С другой стороны, остается ощущение, что принципы построения этих машин содержат излишние ограничения. Разрешение устройству считывать за один раз только одну двоичную цифру ( 0или 1) и передвигаться каждый раз только на один шаг да еще вдоль единственнойодномерной ленты, на первый взгляд, ограничивает возможности машины. Почему бы не разрешить одновременное использование четырех, пяти или, возможно, тысячи разных лент, по которым одновременно двигалось бы большое количество взаимосвязанных считывающих устройств? Почему бы не ввести целую плоскость с нулями и единицами (или, например, трехмерное пространство), вместо того чтобы настаивать на использовании одномерной ленты? Почему бы не использовать другие системы счисления или символы из каких-нибудь более сложных алфавитов? По сути, ни одно из этих изменений ни в малейшей степени не влияет на то, что в принципе может быть достигнуто с помощью машины Тьюринга, хотя некоторые из них отразились бы на экономичности производимых операций (как это наверняка произошло бы, разреши мы использование нескольких лент). Класс осуществляемых операций, попадающих, таким образом, под определение «алгоритма» (или
Мы можем видеть, что нет необходимостив дополнительных лентах, коль скоро устройство может по мере надобности находить свободное место на одной ленте. При этом может потребоваться постоянная перезапись данных с одного места ленты на другое. Это, может быть, «неэффективно», но в принципе не ограничивает возможности машин Тьюринга [44] . Сходным образом, использование более чем одного устройства Тьюринга для параллельных вычислений— идея, ставшая очень популярной в последние годы в связи с попытками более точного моделирования человеческого мозга, — не дает никаких принципиальных преимуществ (хотя при определенных обстоятельствах может увеличиться быстродействие). Использование двух непосредственно не связанных друг с другом устройств не даст выигрыша по сравнению с двумя взаимосвязанными устройствами. Но если два устройства связаны друг с другом, то, в сущности, это уже одно устройство!
44
Один из способов записи информации с двух лент на одну — вставить записи одной из них между записями другой. При этом нечетные отметки на новой ленте могут соответствовать отметкам первой ленты, тогда как четные — отметкам второй. Аналогичная схема работает и для четырех, и для большего числа лент. «Неэффективность» этой процедуры обусловлена тем, что считывающему устройству пришлось бы «прыгать» взад-вперед по ленте, оставляя на ней маркеры как на четных местах, так и на нечетных, с тем чтобы фиксировать свое положение в каждый момент.
А что можно сказать об ограничении Тьюринга, касающегося одномерности ленты? Если мы считаем, что эта лента представляет собой «окружение», то, возможно, мы бы предпочли в качестве такового иметь плоскую поверхность, или, допустим, трехмерное пространство. Может показаться, что плоскость лучше подошла бы для изображения «блок-схемы» вычислений (как в вышеприведенном описании последовательности действий алгоритма Евклида), чем одномерная лента [45] . Однако запись блок-схемы в «одномерной» форме не представляет принципиальных трудностей (например, можно использовать обычное словесное описание). Двумерное плоское изображение дает только удобство и простоту восприятия, но, по сути, ничего не меняет. Всегда есть возможность преобразовать координаты отметки или объекта на двумерной плоскости или в трехмерном пространстве и явным образом отобразить их на одномерной ленте. (Фактически, использование двумерной плоскости полностью эквивалентно использованию двух лент. Две ленты дают две «координаты», которые нужны для определения местоположения точки на двумерной плоскости; аналогично, три ленты могут выполнять ту же роль для точки в трехмерном пространстве.) И хотя эта одномерная запись может вновь оказаться «неэффективной», принципиальные возможности устройства это никак не ограничивает.
45
В согласии с предложенным здесь описанием, эта блок-схема была бы скорее частью «устройства», нежели внешнего окружения — «ленты». На ленте мы до сих пор отображали только числа А, В, А— В, и т. п Однако в дальнейшем нам потребуется также возможность описания и самого устройства в линейной одномерной форме. Как мы увидим далее в связи с универсальной машиной Тьюринга, есть тесная взаимосвязь между свойствами конкретного «устройства» и свойствами возможных «данных» (или «программы») для него. Поэтому удобно в обоих случаях придерживаться одномерной формы записи.
Несмотря на все это, по-прежнему остается вопрос о том, действительно ли понятие машины Тьюринга охватывает все логические или математические операции, которые мы могли бы назвать «механическими». В то время, когда Тьюринг написал свою основополагающую работу, ситуация была гораздо менее ясной, чем сегодня, поэтому Тьюринг справедливо посчитал необходимым предоставить развернутое изложение этого вопроса. Детально рассмотренная Тьюрингом проблема получила дополнительное обоснование благодаря тому, что совершенно независимо от Тьюринга (и на самом деле несколько ранее) американский логик Алонзо Черч (совместно со Стивеном Клини), стремясь найти решение проблемы алгоритмической разрешимости Гильберта, предложил свою схему лямбда-исчисления. Хотя то, что это была всеобъемлющая полностью механическая схема, было не так очевидно, как в случае с подходом Тьюринга, ее несомненным преимуществом была удивительная компактность математической структуры. (Я буду рассматривать замечательный анализ Черча в конце главы.) Независимо от Тьюринга были предложены и другие подходы к решению задачи Гильберта (см. Ганди [1988]), среди которых можно выделить работу американского логика польского происхождения Эмиля Поста (опубликованную несколько позже работы Тьюринга, но содержащую идеи, более близкие идеям Тьюринга, нежели Черча). В скором времени было доказано, что все эти схемы совершенно эквивалентны.
Это значительно укрепило точку зрения, известную как тезис Черча — Тьюринга , которая утверждает,
Числа, отличные от натуральных
В предыдущих параграфах мы рассматривали действия над натуральнымичислами и отметили тот замечательный факт, что машина Тьюринга может оперировать с натуральными числами произвольной величины, несмотря на то, что каждая машина имеет фиксированное и конечноечисло внутренних состояний. Однако часто возникает необходимость в операциях с более сложными числами, такими как отрицательные числа, обыкновенные дроби и бесконечные десятичные дроби. Первые две категории (т. е. числа вида – 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]), а остальные (в действительности абсолютное большинство!) — невычислимыми. Я еще вернусь к этой теме и затрону ряд смежных вопросов в последующих главах. К нам это имеет отношение в связи с вопросом о том, может ли реальный физический объект (например, человеческий мозг) быть адекватно описан в терминах вычислимых математических структур в соответствии с нашими физическими теориями.
Проблема вычислимости важна для математики в целом. Не следует думать, что она относится только к числамкак таковым. Ведь машины Тьюринга могут непосредственно оперировать математическими формулами, например, алгебраическими или тригонометрическими выражениями, или выполнять формальные действия математического анализа. Все, что для этого нужно, это некий способ точного кодирования всех используемых математических символов в виде последовательностей нулей и единиц, которые позволят применить соответствующую машину Тьюринга. Именно это Тьюринг имел в виду, когда он взялся за проблему алгоритмической разрешимости, в которой требуется найти алгоритмическую процедуру для ответа на самые общие математические вопросы. Очень скоро мы вновь обратимся к этой теме.