Роджер Пенроуз - Тени разума. В поисках науки о сознании

• Название: Тени разума. В поисках науки о сознании
• Автор: Роджер Пенроуз
• Издательство: Институт компьютерных исследований
• Жанр: Философия
• ISBN: 5-93972-457-4, 0-19-510646-6

Книга знаменитого физика о современных подходах к изучению деятельности мозга, мыслительных процессов и пр. Излагаются основы математического аппарата — от классической теории (теорема Гёделя) до последних достижений, связанных с квантовыми вычислениями. Книга состоит из двух частей: в первой части обсуждается тезис о невычислимости сознания, во второй части рассматриваются вопросы физики и биологии, необходимые для понимания функционирования реального мозга.

Для широкого круга читателей, интересующихся наукой.

---

Как бы то ни было, высказанные в возражении 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 может оказаться команда 230 → 171R, что означает следующее: «Если машина T находится во внутреннем состоянии 23, а считывающее устройство встречает на ленте символ 0, то его следует заменить символом 1, перейти во внутреннее состояние 17 и переместиться по ленте на один шаг вправо». В этом случае часть «171R» данной команды будет кодироваться последовательностью 100001010110. Разбив ее на участки 1000010.10.110, мы видим, что первый из них представляет собой расширенную двоичную запись числа 17, второй кодирует отметку 1 на ленте, а третий — команду «переместиться на шаг вправо». А как нам описать предыдущее внутреннее состояние (в данном случае 23) и считываемую в соответствующий момент отметку на ленте (в данном случае 0)? При желании можно задать их так же явно с помощью расширенной двоичной записи. Однако на самом деле в этом нет необходимости, поскольку для этого будет достаточно упорядочить различные команды в виде цифровой последовательности (например, такой: 00 →, 01 →, 10 →, 11 →, 20 →, 21 →, 30 →, …).

К этому, в сущности, и сводится все кодирование машин Тьюринга, предложенное в НРК, однако для завершенности картины необходимо добавить еще несколько пунктов. Прежде всего, следует проследить за тем, чтобы каждому внутреннему состоянию, действующему на отметки 0 и 1 (не забывая, впрочем, о том, что команда для внутреннего состояния с наибольшим номером, действующая на 1, оказывается необходимой не всегда), была сопоставлена какая-либо команда. Если та или иная команда вообще не используется в программе, то необходимо заменить ее «пустышкой». Предположим, например, что в ходе выполнения программы внутреннему состоянию 23 нигде не придется сталкиваться с отметкой 1 — соответствующая команда-пустышка в этом случае может иметь следующий вид: 231 → 00R.

Согласно вышеприведенным предписаниям, в кодированной спецификации машины Тьюринга на ленте пара символов 00 должна быть представлена последовательностью 00, однако можно поступить более экономно и записать просто 0, что явится ничуть не менее однозначным разделителем двух последовательностей, составленных из более чем одного символа 1 подряд[18]. Машина Тьюринга начинает работу, находясь во внутреннем состоянии 0; считывающее устройство движется по ленте, сохраняя это внутреннее состояние до тех пор, пока не встретит первый символ 1. Это обусловлено допущением, что в набор команд машины Тьюринга всегда входит операция 00 → 00R. Таким образом, в действительной спецификации машины Тьюринга в виде последовательности 0 и 1 явного задания этой команды не требуется; вместо этого мы начнем с команды 01 → X, где X обозначает первую нетривиальную операцию запущенной машины, т.е. первый символ 1, встретившийся ей на ленте. Это значит, что начальную последовательность 110 (команду → 00R), которая в противном случае непременно присутствовала бы в определяющей машину Тьюринга последовательности, можно спокойно удалить. Более того, в такой спецификации мы будем всегда удалять и завершающую последовательность 110, так как она одинакова для всех машин Тьюринга.