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

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

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

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

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

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

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

С учетом вышесказанного решение задачи (А) может происходить следующим образом. Мы поочередно проверяем каждое натуральное число, начиная с 0, на предмет того, не является ли оно суммой трех квадратов. При этом, разумеется, рассматриваются только те квадраты, величина которых не превышает самого числа. Таким образом, для каждого натурального числа необходимо проверить некоторое конечное количество квадратов. Отыскав тройку квадратов, составляющих в сумме данное число, переходим к следующему натуральному числу и снова ищем среди квадратов (не превышающих по величине рассматриваемое число) такие три, которые дают в сумме это самое число. Вычисление завершается лишь тогда, когда мы находим натуральное число, которое невозможно получить путем сложения любых трех квадратов. Попробуем применить описанную процедуру на практике и начнем наше вычисление с нуля. Нуль равен 0^>2 + 0^>2 + 0^>2, что, безусловно, является суммой трех квадратов. Далее рассматриваем единицу и находим, что она не равна 0^>2 + 0^>2 + 0^>2, однако равна 0^>2 + 0^>2 + 1^>2. Переходим к числу 2 и выясняем, что оно не равно ни 0^>2 + 0^>2 + 0^>2, ни 0^>2 + 0^>2 + 1^>2, но равно 0^>2 + 1^>2 + 1^>2. Затем следует число 3 и сумма 3 = 1^>2 + 1^>2 + 1^>2; далее — число 4 и сумма 4 = 0^>2 + 0^>2 + 2^>2; после 5 = 0^>2 + 1^>2 + 2^>2 и 6 = 1^>2 + 1^>2 + 2^>2 переходим к 7, и тут обнаруживается, что ни одна из троек квадратов (всех возможных троек квадратов, каждый из которых не превышает 7)

не дает в сумме 7. На этом этапе вычисление завершается, а мы делаем вывод: 7 есть одно из искомых чисел, так как оно не является суммой квадратов трех чисел.

Будем считать, что с задачей (А) нам просто повезло. Попробуем решить еще одну:

На этот раз, добравшись до числа 7, мы находим, что в виде суммы квадратов четырех чисел его представить вполне возможно: 7 = 1^>2 + 1^>2 + 1^>2 + 2^>2, поэтому мы переходим к числу 8 (сумма 8 = 0^>2 + 0^>2 + 2^>2 + 2^>2), далее — 9 (сумма 9 = 0