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

Те из вас, кто читал мою предыдущую книгу «Новый разум короля» (см. НРК, глава 2), возможно, припомнят, что алгоритм там определяется как процедура, которую способна выполнить машина Тьюринга, или, если угодно, математически идеализированная вычислительная машина. Такая машина функционирует в пошаговом режиме, причем каждый ее шаг полностью задается нанесенной на рабочую «ленту» меткой, которую (метку) машина «считывает» в соответствующий момент времени, и «внутренним состоянием» машины (дискретно определенным) на этот момент. Количество различных разрешенных внутренних состояний конечно, общее число меток на ленте также должно быть конечным, хотя сама лента по длине не ограничена. Машина начинает работу с какого-то определенного состояния, которое мы обозначим, например, нулем «0», команды же подаются на ленте в виде, скажем, двоичного числа (т.е. последовательности нулей «0» и единиц «1»). Далее машина начинает считывать эти команды, передвигая ленту (либо, что то же самое, перемещаясь вдоль ленты) некоторым определенным образом, согласно встроенным пошаговым инструкциям, при этом действие машины на каждом этапе работы определяется ее внутренним состоянием и конкретным символом, считываемым на данном этапе с ленты. Руководствуясь все теми же встроенными инструкциями, машина может стирать имеющиеся метки или ставить новые. В таком духе машина продолжает работать до тех пор, пока не достигнет особой команды «STOP», — именно в этот момент (и никак не раньше) машина прекращает работу, а мы можем увидеть на ленте ответ на выполнявшееся вычисление. Вот и все, можно задавать машине новую задачу.

Можно представить себе некую особую машину Тьюринга, которая способна имитировать действие любой возможной машины Тьюринга. Такие машины Тьюринга называют универсальными. Иными словами, любая отдельно взятая универсальная машина Тьюринга оказывается в состоянии выполнить любое вычисление (или алгоритм), какое нам только может прийти в голову. Хотя внутреннее устройство современного компьютера весьма отличается от устройства описанной выше конструкции (а его внутренняя «рабочая область», пусть и очень велика, все же не бесконечна, в отличие от идеализированной ленты машины Тьюринга), все современные универсальные компьютеры представляют собой, в сущности, универсальные машины Тьюринга.

2.2. Вычисления

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

(А) Найти число, не являющееся суммой квадратов трех чисел.

Под «числом» в данном случае я подразумеваю «натуральное число», т.е. число из ряда

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ….

Под квадратом числа понимается результат умножения натурального числа на само себя, т.е. число из ряда

0, 1, 4, 9, 16, 25, 36, …;

представленные в этом ряду числа получены следующим образом:

0 × 0 = 0², 1 × 1 = 1

², 2 × 2 = 2², 3 × 3 = 3², 4 × 4 = 4², 5 × 5 = 5²

, 6 × 6 = 6², ….

Такие числа называются «квадратами», поскольку их можно представить в виде квадратных матриц (пустой матрицей в начале строки обозначен 0):