Машина з натуральнозначними регістрами

Машина з натуральнозначними регістрами (МНР) — абстрактна обчислювальна машина.

МНР складається із, взагалі кажучи, нескінченної кількості натуральночисельних регістрів, пронумерованих з нуля. Позначатимемо їх R[0], R[1], …, R[n], …

Значення всіх регістрів (R[0], R[1], …, R[n], …) утворюють конфігурацію. Виконання МНР-програми починається із початкової конфігурації і закінчується в фінальній конфігурації. Кажуть, що МНР-програма обчислює n-арну функцію f, задану таким чином:

f(x₁, x₂, …, x_n) = { значення R[0] фінальної конфігурації при роботі над початковою конфігурацією (x₁, x₂, …, x_n, 0, 0, 0, …), якщо програма зупиниться; невизначено інакше }

Програми для МНР складаються зі скінченної кількості команд чотирьох типів:

1. Z(n) — обнулити регістр з номером n (R[n]:=0);
2. S(n) — інкремент (збільшення на одиницю) n-того регістра (R[n]:=R[n]+1);
3. T(m, n) — копіювати вміст регістра m в n (R[n]:=R[m]);
4. J(m, n, q) — якщо R[m]=R[n], то наступною виконувати команду з номером q, інакше — наступну за списком.

Виконання однієї команди називають кроком МНР.

Команди нумеруються, починаючи з одиниці. Виконання програми закінчується, якщо наступна команда відсутня.

МНР-програми Тюрінг-повні. А втім, набір команд є надлишковим; копіювання значень регістрів можна реалізувати без команд типу T. А саме, будь-яка команда вигляду q) T(m, n) еквівалентна фрагменту

q+0) Z(n)
q+1) J(m,n,q+4)
q+2) S(n)
q+3) J(0,0,q+1)

Приклади

• МНР-програма, що обчислює нескінченну кількість всюди невизначених функцій, які відрізняються арністю:

1) J(0,0,1)

• МНР-програма, що обчислює функцію f(x, y) = x+y:

1) J(1,2,5)
2) S(0)
3) S(2)
4) J(0,0,1)

Початкова конфігурація — (x, y, 0, 0, …). Якщо y=0, то на першому ж кроці спрацьовує перехід і виконання програми завершується в конфігурації (x, …). Результат виконання — x = x+0 = f(x, y). Взагалі кажучи, команди 1) та 4) організовують цикл, який проводить програму по конфігураціям вигляду (x+i, y, i, 0, 0, …). Цикл продовжується, доки значення i=R[2] не стане рівним y=R[1] — ,а отже, R[0] не стане рівним x+y. Бачимо, що програма дійсно обчислює функцію f(x, y) = x+y.

• МНР-програма, що обчислює функцію f(x, y) = x·y:

1) J(3,1,9)
2) J(0,2,6)
3) S(2)
4) S(4)
5) J(0,0,2)
6) Z(2)
7) S(3)
8) J(0,0,1)
9) T(4,0)

Тут можемо побачити два вкладені цикли; внутрішній додає R[0] до R[4], зовнішній запускає цю дію y разів. Відповідно, усі конфігурації мають вигляд (x, y, i, j, r, 0, 0, …), 0 ≤ i ≤ x, 0 ≤ j ≤ y, r = x·j+i. Звертаємо увагу на команду 6), яка обертає в 0 лічильник i, та команду 9), яка копіює результат обчислення в R[0].