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



         

Глава 3. Как работают вычислительные машины - стр. 13


В принципе, машина Тьюринга, находящаяся в некотором состоянии, скажем, 19 и просматривающая некоторый символ, например "1", должна прочесть все введенные в ее программу наборы из пяти элементов, все время задаваясь, так сказать, вопросом, является ли считываемая пятерка (правило) той самой пятеркой, которая применима к состоянию 19. Когда машина обнаруживает пятерку, соответствующую ее текущему состоянию и просматриваемому символу, она перезаписывает этот символ, передвигает ленту и (возможно) изменяет свое состояние. Затем поиск начинается снова. Однако если пятерки хранятся в адресуемой памяти, то поиска подходящей пятерки можно избежать или по крайней мере уменьшить его продолжительность. Допустим, что все пятерки, связанные с некоторым определенным состоянием, требуют, скажем, 100 байт памяти, и начало первой пятерки приходится на регистр 1000. В таком случае набор, соответствующий состоянию 19, будет содержаться в памяти, начиная с регистра с номером 1000+(19-1) x 100, т. е. регистра 2800. Таким образом, понятие состояния полностью переходит в понятие адреса, по крайней мере в данном контексте.

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

Требуется вычислить квадратные корни чисел. (Это означает, что если задано некоторое число, скажем, 25, то требуется определить, какое число, умноженное само на себя, даст заданное. Квадратный корень из 25 равен 5, так как 5 x 5 - 25.) Допустим, что у нас есть добросовестный слуга (человек), без устали исполняющий любую данную ему команду. Известен алгоритм вычисления квадратных корней из положительных чисел. Если задано число n, то его квадратный корень вычисляется следующим образом:




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