Машина с неограниченными регистрами

Машина с неограниченными регистрами

Машина с неограниченными регистрами имеет бесконечно много регистров памяти R1, R2, ..., а в каждом регистре может храниться сколь угодно большое целое неотрицательное число.

Машина с неограниченными регистрами (МНР) — это своего рода идеализированный компьютер. МНР имеет бесконечно много регистров R_1, R₂, в каждом из которых в любой момент времени записано некоторое натуральное число. Число, находящееся в регистре R_n, будем обозначать r_n. Содержимое регистров может меняться при выполнении некоторой команды, Конечный упорядоченный список команд образует программу, Будем предполагать, что команды занумерованы числами 1,2,3,...

Команды бывают четырех типов:

1. 1) команда обнуления имеет вид Z(n), n ∈ {1,2,3, ...}. Выполнение такой команды заменяет содержимое регистра R_n на 0, не затрагивая другие регистры. Используя оператор присваивания, команду Z(n) можно записать так: r_n:= 0;
2. 2) команда прибавления единицы имеет вид S(n), n ∈ {1,2,3, ...}. Выполнение такой команды увеличивает содержимое регистра R_n на 1, не затрагивая другие регистры. С помощью оператора присваивания команда S(n) записывается так: r_n := r_n + 1;
3. 3) команда переадресации имеет вид Т(m, n), m, n ∈ {1,2,3, ...}. Выполнение такой команды заменяет содержимое регистра R_n числом r_m находящимся в регистре R_m, не затрагивая другие регистры (в том числе регистр R_m). Команду Т(m, n) можно записать так: r_n := r_m ;
4. 4) команда условного перехода имеет вид  J (m,n,q), m, n, q ∈ {1,2,3, ...}. Выполнение такой команды состоит в следующем. Сравнивается содержимое регистров R_m и R_n. При r_m = r_n машина переходит к выполнению q-й команды программы; при r_m ≠ r_n — к выполнению следующей команды. Если в результате исполнения команды требуется выполнить команды с номером, превосходящим число команд в программе, машина прекращает работу. Команду J(m,n, д) можно записать так: IF r_m == r_n GOTO q.

Команды обнуления, прибавления единицы и переадресации называются арифметическими. 

Структура и функционирование

Составные части.

1) Регистры R₁, R₂, R₃,..., в которых содержатся соответственно натуральные числа r₁, r₂, r₃,...

Число регистров бесконечно, но только конечное множество регистров R₁, R₂,...,R_k содержит числа, отличные от нуля. Все остальные регистры R_k+1, R_k+2,... заполнены нулями.

.
Машина с неограниченными регистрами, как и произвольный алгоритм, работает по тактам: такт 1, такт 2, ... Первый такт работы МНР с программой I₁, I₂,...,I₈ — выполнение первой команды I₁. Затем выполняются команды I₂, I₃,... Этот последовательный порядок выполнения команд продолжается до тех пор, пока не встретится команда J (m, n, q), которая может изменить естественный порядок выполнения команд.

Условие остановки. Машина останавливается тогда и только тогда, когда невозможно выполнить очередную предписанную команду. Это означает, что МНР только что совершила i-вый такт работы и следующим  i + 1 тактом должна выполнить несуществующую команду. Эта ситуация при выполнении программы I₁, I₂,...,I₈ возникает ровно в одном из трех следующих случаев:

1. 1) Если в i-вом такте выполнена I₈ — последняя команда программы и эта команда не является командой условного перехода, тогда следующим i +1 тактом должна выполняться несуществующая команда I₈₊₁.
2. 2) Если в i-вом такте выполнена команда условного перехода J (m, n, q), где r_m = r_n  и q > s тогда следующим i + 1тактом должна выполняться несуществующая команда I_q.
3. 3) Если в i-вом такте выполнена I₈ — последняя команда программы и эта команда является командой условного перехода J (m, n, q) при r_m ≠ r_n,тогда следующим i + 1 тактом должна выполняться несуществующая команда I₈₊₁.

Крупский В.Н. Теория алгоритмов : учеб, пособие для студ. вузов / В. Н. Крупский, В. Е. Плиско. — М.: Издательский центр «Академия», 2009. — 208 с.