23.05.2017 13:15

Вычислительные машины с бесконечными регистрами

Вычислительные машины с бесконечными регистрами

Человек использует алгоритмы в своей жизни с давних пор. Например, алгоритм Евклида для нахождения наибольшего делителя двух чисел известен уже несколько тысяч лет. Важность алгоритма заключается в том “удобстве”, которое он несет с собой. Если у задачи существует алгоритм для ее решения, то такие задачи решаются быстрее и не требуют для своего решения значительных усилий. Поэтому вполне естественно, что люди ставят перед собой задачу нахождения алгоритмов. Но не все задачи имеют алгоритмическое решение и доказать такой факт имея только интуитивное понятие алгоритма было невозможно.

Такая возможность появилась совсем недавно, в 30-х годах XX века в результате работы ученых был предложен подход для построения точного математического определения алгоритма. Подход этот связан с построением так называемых универсальных вычислительных машин. Самой известной среди них является, пожалуй, машина Тьюринга. Но к сожалению трудоемкость работы с такими машинами была очень большой. Поэтому появление в 1963 году машины с бесконечными регистрами (МБР) было большим шагом вперед, поскольку позволило заметно упростить процесс построения алгоритмов. Авторами МБР являются два ученых Шепердсон (Бристольский университет, Англия) и Старджис (Беркли, Калифорния, США). Несмотря на то, что машина обладает всего 4 типами команд, на ней могут быть реализованы все возможные алгоритмы. Базовые типы команд МБР:
1. нулевая функция Z(n): rn = 0;
2. прибавление единицы S(n): rn = rn + 1;
3. копирование T(m, n): rn = rm ;
4. условный переход J(m, n, q): Если rm = rn то идти к инструкции с
номером q, иначе идти к следующей инструкции.

Как оказывается, такой набор команд не является необходимым.

Теорема. Любую программу, использующую команду копирования T(m,n) можно написать без ее использования.

Тем не менее, использование команды копирования представляется удобным. Так же для удобства можно вводить новые команды, не использовавшиеся в базовом определении МБР, например, можно ввести команду вычитания единицы M(m,n).

Теорема. Любая программа, использующая команду вычитания M(m,n) может быть написана без ее использования.

Маслова Е.

Вычислительные машины с бесконечными регистрами

Опубликовано 23.05.2017 13:15 | Просмотров: 1060 | Блог » RSS