§1. Эффективная вычислимость. Границы применимости

Как реальные, так и абстрактные вычислительные машины, созданные или придуманные к настоящему времени, плохо приспособлены для решения задачи моделирования процессуальной, динамической стороны окружающего нас мира.

В качестве основы для сравнения возьмем три группы свойств, определяющих границы применимости компьютеров указанных типов при описании процессов.

1. Синтаксические ограничения.
2. Ограничения по памяти.
3. Ограничения на порядковые типы процессов.

Перейдем теперь к свойствам внутри каждой из перечисленных групп.

1. Синтаксическая сложность. Программирование как реальных, так и абстрактных компьютеров — это почти всегда нагромождение синтаксических конструкций для выражения самых простых вещей. Например, в Паскале вы не должны писать X:=Y, если X имеет тип INTEGER (целого числа), а Y — тип REAL (действительного числа). Вместо этого приходится писать X:=TRUNC(Y), где «TRUNC» — функция преобразования типа REAL в тип INTEGER. Предметом особой гордости разработчиков системы «Турбо-Паскаль» служит наличие в этой системе не одного, как в стандартном Паскале, а нескольких целочисленных и вещественных типов, что тоже отнюдь не упрощает синтаксис. В других языках программирования дела обстоят не лучшим образом. Не лучше они и в случае программирования абстрактных вычислительных машин, программы для которых скорее напоминают программы на ассемблере, чем программы на языках высокого уровня. Возьмем в качестве примера программу для машины с неограниченными регистрами, складывающую два целых числа X и Y: I1 J(3,2,5); I2 S(1); I3 S(3); I4 J(1,1,1).
   Излишне говорить, что программы, описывающие менее тривиальные процессы, чем процесс сложения, будут содержать более длинные и труднообозримые цепочки команд.

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