6.1 Новая модель алгоритма вычислений.

Новая модель алгоритма вычислений представляет собой машину с неограниченными регистрами (МНР).

Определение. МНР – машина с бесконечной лентой ячеек, которые пронумерованы от 1 до ∞, причем в каждой ячейке содержится некоторое натуральное число.

Машина работает по программе, написанной на языке МНР. Язык МНР состоит из команд 4 типов

В программе на каждой строке находится по одной программе.

Теорема 6.1 Все что можно вычислить, можно вычислить на МНР.

Доказательство. Научимся моделировать на МНР работу машины Тьюринга ( а все что можно вычислить – можно вычислить на машине Тьюринга(тезис Черча)).

Теорема доказана.

Замечание о трудоемкости вычисления на МНР.

С одной стороны на МНР более быстрый доступ к памяти по сравнению с МТ( при работе на МТ мы за один шаг смещаемся только в соседнюю ячейку, а при работе на МНР за один шаг можем переместиться в любую), другой стороны, на МНР значение переменной за одно действие изменяется всего на 1, так что некоторые программы будут быстрее выполнятся на машине Тьюринга, некоторые на МНР.

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

Пример. Программа сложения двух чисел:

Вход:

1 2 3 4 5

Выход:

1 2 3 4

Рисунок 6.1 Иллюстрация работы программы

Программа

1: T(1,3)

2: Z(4)

3: S(3)

4: S(4)

5: J(2,4,7)

6: J(1,1,3) – фактический оператор безусловного перехода

7: -------- - пустой оператор (выход), т. е . любой оператор, ничего не меняющий в третьей ячейке