Тени разума. В поисках науки о сознании
Шрифт:
Вышеприведенная процедура была впервые предложена Аланом Тьюрингом в его докторской диссертации (а опубликована в [ 368 ]) {36} ; там же Тьюринг показал, что любоеистинное 1– высказывание можно, в некотором смысле, доказать с помощью многократной гёделизаций, подобной описанной нами. (См. также [ 117 ].) Впрочем, воспользоваться этим для получения механической процедуры установления истинности 1– высказываний нам не удастся по той простой причине, что механически систематизировать гёделизацию невозможно. Более того, невозможность «автоматизации» процедуры гёделизаций как раз и выводитсяиз результата Тьюринга. А в §2.5 мы уже показали, что общее установление истинности (либо ложности) 1– высказываний невозможно произвести с помощью каких бы то ни было алгоритмических процедур. Так что в поисках систематической процедуры, не доступной тем вычислительным соображениям, которые мы рассматривали до настоящего момента,
Q20. Реальная ценность математического понимания состоит, безусловно, не в том, что благодаря ему мы способны выполнять невычислимые действия, а в том, что оно позволяет нам заменить невероятно сложные вычисления сравнительно простым пониманием. Иными словами, разве не правда, что, используя разум, мы, скорее, «срезаем углы» в смысле теории сложности, а вовсе не «выскакиваем» за пределы вычислимого?
Я вполне готов поверить в то, что на практикеинтуиция математика гораздо чаще используется для «обхода» вычислительной сложности, чем невычислимости. Как-никак математики по природе своей склонны к лени, а потому зачастую стараются изыскать всяческие способы избежать вычислений (пусть даже им придется в итоге выполнить значительно более сложную мыслительную работу, нежели потребовало бы собственно вычисление). Часто случается так, что попытки заставить компьютеры бездумно штамповать теоремы даже умеренно сложных формальных систем быстро загоняют эти самые компьютеры в ловушку фактически безнадежной вычислительной сложности, тогда как математик-человек, вооруженный пониманием смысла, лежащего в основе правил такой системы, без особого труда получит в рамках этой системы множество интересных результатов {37} .
Причина того, что в своих доказательствах я рассматривал не сложность, а невычислимость, заключается в том, что только с помощью последней мне удалось сформулировать необходимые для доказательства сильные утверждения. Не исключено, что в работе большинства математиков вопросы невычислимости играют весьма незначительную роль, если вообще играют. Однако суть не в этом. Я глубоко убежден, что понимание (в частности, математическое) представляет собой нечто, недоступное вычислению, а одной из немногих возможностей вообще подступиться ко всем этим вопросам является как раз доказательство Гёделя(—Тьюринга). Никто не отрицает, что наши математические интуиция и понимание нередко используются для получения результатов, достижимых, в принципе, и вычислительным путем, — но и здесь слепое, не отягощенное пониманием, вычисление может оказаться неэффективным настолько, что попросту не будет работать (см. §3.26 ). Однако рассмотрение всех таких случаев представляется мне неизмеримо более сложным подходом, нежели обращение к общей невычислимости.
Как бы то ни было, высказанные в возражении Q20 соображения, пусть и справедливые, все же ни в коей мере не противоречат выводу G.
Приложение A: Гёделизирующая машина Тьюринга в явном виде
Допустим, что у нас имеется некая алгоритмическая процедура A, которая, как нам известно, корректно устанавливает незавершаемость тех или иных вычислений. Мы получим вполне явную процедуру для построения на основе процедуры A конкретного вычисления C, для которого Aоказывается неадекватной; при этом мы сможем убедиться, что вычисление C действительно незавершается. Приняв это явное выражение для C, мы сможем определить степень его сложности и сравнить ее со сложностью процедуры A, чего требуют аргументы §2.6 (возражение Q8) и §3.20 .
Для определенности я воспользуюсь спецификациями той конкретной машины Тьюринга, которую я описал в НРК. Подробное описание этих спецификаций читатель сможет найти в названной работе. Здесь же я дам лишь краткое описание, которого вполне должно хватить для наших настоящих целей.
Машина Тьюринга имеет конечное число внутренних состояний, но производит все операции на бесконечной ленте. Эта лента представляет собой линейную последовательность «ячеек», причем каждая ячейка может быть маркированной или пустой, а общее количество отметок на ленте — величина конечная. Обозначим каждую маркированную ячейку символом 1, а каждую пустую ячейку — 0. В машине Тьюринга имеется также считывающее устройство, которое поочередно рассматривает отметки и, в явной зависимости от внутреннего состояния машины Тьюринга и характера рассматриваемой в данный момент отметки, определяет дальнейшие действия машины по следующим трем пунктам: (I) следует ли изменить рассматриваемую в данный момент отметку; (II) каким будет новое внутреннее состояние машины; (III) должно ли устройство сдвинуться по ленте на один шаг вправо (обозначим это действие через R) или влево (обозначим через L), или же на один шаг вправо с остановкой машины ( STOP). Когда машина, в конце концов, остановится, на ленте слева от считывающего устройства будет представлен в виде последовательности символов 0и 1ответ на выполненное ею вычисление. Изначально лента должна быть абсолютно чистой, за исключением отметок, описывающих исходные данные (в виде конечной строки символов 1и 0), над которыми машина и будет выполнять свои операции. Считывающее устройство в начале работы располагается слева от всех
При представлении на ленте натуральных чисел (будь то входные или выходные данные) иногда удобнее использовать так называемую расширенную двоичнуюзапись, согласно которой число, в сущности, записывается в обычной двоичной системе счисления, только двоичный знак «1» представляется символами 10, а двоичный знак «0» — символом 0. Таким образом, мы получаем следующую схему перевода десятичных чисел в расширенные двоичные:
0 <-> 0
1 <-> 10
2 <-> 100
3 <-> 1010
4 <-> 1000
5 <-> 10010
6 <-> 10100
7 <-> 101010
8 <-> 10000
9 <-> 100010
10 <-> 100100
11 <-> 1001010
12 <-> 101000
13 <-> 1010010
14 <-> 1010100
15 <-> 10101010
16 <-> 100000
17 <-> 1000010
и т.д.
Заметим, что в расширенной двоичной записи символы 1никогда не встречаются рядом. Таким образом, последовательность из двух или более 1вполне может послужить сигналом о начале и конце записи натурального числа. То есть для записи всевозможных команд на ленте мы можем использовать последовательности типа 110, 1110, 11110и т.д.
Отметки на ленте также можно использовать для спецификации конкретных машин Тьюринга. Это необходимо, когда мы рассматриваем работу универсальноймашины Тьюринга U. Универсальная машина Uработает с лентой, начальная часть которой содержит подробную спецификацию некоторой конкретной машины Тьюринга T, которую универсальной машине предстоит смоделировать. Данные, с которыми должна работать сама машина T, подаются в Uвслед за тем участком ленты, который определяет машину T. Для спецификации машины Tможно использовать последовательности 110, 1110и 11110, которые будут обозначать, соответственно, различные команды для считывающего устройства машины T, например: переместиться по ленте на один шаг вправо, на один шаг влево, либо остановиться, сдвинувшись на один шаг вправо:
R<-> 110
L<-> 1110
STOP <-> 11110.
Каждой такой команде предшествует либо символ 0, либо последовательность 10, что означает, что считывающее устройство должно пометить ленту, соответственно, либо символом 0, либо 1, заменив тот символ, который оно только что считало. Непосредственно перед вышеупомянутыми 0или 10 располагается расширенное двоичное выражение числа, описывающего следующее внутреннее состояние, в которое должна перейти машина Тьюринга согласно этой самой команде. (Отметим, что внутренние состояния, поскольку количество их конечно, можно обозначать последовательными натуральными числами 0, 1, 2, 3, 4, 5, 6, …, N. При кодировании на ленте для обозначения этих чисел будет использоваться расширенная двоичная запись.)
Конкретная команда, к которой относится данная операция, определяется внутренним состоянием машины перед началом считывания ленты и собственно символами 0или 1, которые наше устройство при следующем шаге считает и, возможно, изменит. Например, частью описания машины T может оказаться команда 23 0– > 17 1R, что означает следующее: «Если машина Tнаходится во внутреннем состоянии 23, а считывающее устройство встречает на ленте символ 0, то его следует заменить символом 1, перейти во внутреннее состояние 17 и переместиться по ленте на один шаг вправо». В этом случае часть «17 1R» данной команды будет кодироваться последовательностью 100001010110. Разбив ее на участки 1000010.10.110, мы видим, что первый из них представляет собой расширенную двоичную запись числа 17, второй кодирует отметку 1на ленте, а третий — команду «переместиться на шаг вправо». А как нам описать предыдущее внутреннее состояние (в данном случае 23) и считываемую в соответствующий момент отметку на ленте (в данном случае 0)? При желании можно задать их так же явно с помощью расширенной двоичной записи. Однако на самом деле в этом нет необходимости, поскольку для этого будет достаточно упорядочить различные команды в виде цифровой последовательности (например, такой: 0 0– >, 0 1– >, 1 0– >, 1 1– >, 2 0– >, 2 1– >, 3 0– >, …).
К этому, в сущности, и сводится все кодирование машин Тьюринга, предложенное в НРК, однако для завершенности картины необходимо добавить еще несколько пунктов. Прежде всего, следует проследить за тем, чтобы каждому внутреннему состоянию, действующему на отметки 0и 1(не забывая, впрочем, о том, что команда для внутреннего состояния с наибольшим номером, действующая на 1, оказывается необходимой не всегда), была сопоставлена какая-либо команда. Если та или иная команда вообще не используется в программе, то необходимо заменить ее «пустышкой». Предположим, например, что в ходе выполнения программы внутреннему состоянию 23 нигде не придется сталкиваться с отметкой 1— соответствующая команда-пустышка в этом случае может иметь следующий вид: 23 1– > 0 0R.