Тени разума. В поисках науки о сознании

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