Возможности вычислительных машин и человеческий разум



         

Глава 2. Откуда возникает мощь вычислительной машины - стр. 31


Но машину такого рода построить нельзя. Этот и множество подобных "неразрешимых" вопросов кладут некоторый предел тому, что вычислительные машины могут делать. Это, естественно, логическое ограничение, являющееся препятствием не только для вычислительных машин, но и для всякого вычисляющего - будь то человек или механическое устройство. Следует также отметить, что все множество неразрешимых проблем не так уж интересно с практической точки зрения; все вопросы такого рода чрезвычайно общи. Если мы имеем дело с каким-то определенным вычислительным процессом и хотим выяснить, закончится он когда-нибудь или нет, то обычно можно построить некоторую процедуру, позволяющую установить это. Но невозможно иметь некоторую машину или, что то же самое, эффективную процедуру, позволяющую отвечать на этот вопрос для любой процедуры в общем случае.

Во-вторых, некоторая эффективная процедура может в принципе позволить выполнить определенные вычисления, но для этого требуется так много времени, что процедура оказывается практически бесполезной. Например, обратимся к шахматам. Учитывая правило, согласно которому игра прерывается, если некоторая позиция на доске возникает три раза, можно определенно считать, что шахматы - конечная игра. Следовательно, в принципе возможно написать некоторую процедуру порождения списка всех партий, ход за ходом, которые вообще могут быть разыграны. Для завершения этого вычислительного процесса потребовалась бы, однако, вечность даже при использовании самых быстрых вычислительных машин, которые только можно себе вообразить. Это пример практически бесполезной процедуры. В самом деле, до сих пор мы обсуждали процедуры так, как будто время, необходимое для их реализации, т. е. для завершения соответствующей вычислительной задачи, несущественно. Подобный подход приемлем до тех пор, пока мы занимаемся абстрактными играми. В реальной жизни время имеет значение. Следует, в частности, иметь в виду, что, когда одна вычислительная машина имитирует другую, она должна на каждый такт работы имитируемой машины затратить множество сопряженных со значительными затратами времени тактов своей работы.


Содержание  Назад  Вперед