Машина з натуральнозначними регістрами (МНР) — абстрактна обчислювальна машина.
МНР складається із, взагалі кажучи, нескінченної кількості натуральночисельних регістрів, пронумерованих з нуля. Позначатимемо їх R[0], R[1], …, R[n], …
Значення всіх регістрів (R[0], R[1], …, R[n], …) утворюють конфігурацію. Виконання МНР-програми починається із початкової конфігурації і закінчується в фінальній конфігурації. Кажуть, що МНР-програма обчислює n-арну функцію f, задану таким чином:
f(x1, x2, …, xn) = { значення R[0] фінальної конфігурації при роботі над початковою конфігурацією (x1, x2, …, xn, 0, 0, 0, …), якщо програма зупиниться; невизначено інакше }
Програми для МНР складаються зі скінченної кількості команд чотирьох типів:
- Z(n) — обнулити регістр з номером n (R[n]:=0);
- S(n) — інкремент (збільшення на одиницю) n-того регістра (R[n]:=R[n]+1);
- T(m, n) — копіювати вміст регістра m в n (R[n]:=R[m]);
- 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].
Примітки
- тим не менше, очевидно, що програма зі скінченної кількості команд може використати лише скінченну кількість регістрів.
- в теорії алгоритмів нуль прийнято включати до множини натуральних чисел.
Посилання
Ця стаття не містить . (березень 2020) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U Vikipediyi ye statti pro inshi znachennya cogo termina MNR znachennya Mashina z naturalnoznachnimi registrami MNR abstraktna obchislyuvalna mashina MNR skladayetsya iz vzagali kazhuchi neskinchennoyi kilkosti naturalnochiselnih registriv pronumerovanih z nulya Poznachatimemo yih R 0 R 1 R n Znachennya vsih registriv R 0 R 1 R n utvoryuyut konfiguraciyu Vikonannya MNR programi pochinayetsya iz pochatkovoyi konfiguraciyi i zakinchuyetsya v finalnij konfiguraciyi Kazhut sho MNR programa obchislyuye n arnu funkciyu f zadanu takim chinom f x1 x2 xn znachennya R 0 finalnoyi konfiguraciyi pri roboti nad pochatkovoyu konfiguraciyeyu x1 x2 xn 0 0 0 yaksho programa zupinitsya neviznacheno inakshe Programi dlya MNR skladayutsya zi skinchennoyi kilkosti komand chotiroh tipiv Z n obnuliti registr z nomerom n R n 0 S n inkrement zbilshennya na odinicyu n togo registra R n R n 1 T m n kopiyuvati vmist registra m v n R n R m J m n q yaksho R m R n to nastupnoyu vikonuvati komandu z nomerom q inakshe nastupnu za spiskom Vikonannya odniyeyi komandi nazivayut krokom MNR Komandi numeruyutsya pochinayuchi z odinici Vikonannya programi zakinchuyetsya yaksho nastupna komanda vidsutnya MNR programi Tyuring povni A vtim nabir komand ye nadlishkovim kopiyuvannya znachen registriv mozhna realizuvati bez komand tipu T A same bud yaka komanda viglyadu q T m n ekvivalentna fragmentu q 0 Z n q 1 J m n q 4 q 2 S n q 3 J 0 0 q 1 PrikladiMNR programa sho obchislyuye neskinchennu kilkist vsyudi neviznachenih funkcij yaki vidriznyayutsya arnistyu 1 J 0 0 1 MNR programa sho obchislyuye funkciyu f x y x y 1 J 1 2 5 2 S 0 3 S 2 4 J 0 0 1 Pochatkova konfiguraciya x y 0 0 Yaksho y 0 to na pershomu zh kroci spracovuye perehid i vikonannya programi zavershuyetsya v konfiguraciyi x Rezultat vikonannya x x 0 f x y Vzagali kazhuchi komandi 1 ta 4 organizovuyut cikl yakij provodit programu po konfiguraciyam viglyadu x i y i 0 0 Cikl prodovzhuyetsya doki znachennya i R 2 ne stane rivnim y R 1 a otzhe R 0 ne stane rivnim x y Bachimo sho programa dijsno obchislyuye funkciyu f x y x y MNR programa sho obchislyuye funkciyu 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 Tut mozhemo pobachiti dva vkladeni cikli vnutrishnij dodaye R 0 do R 4 zovnishnij zapuskaye cyu diyu y raziv Vidpovidno usi konfiguraciyi mayut viglyad x y i j r 0 0 0 i x 0 j y r x j i Zvertayemo uvagu na komandu 6 yaka obertaye v 0 lichilnik i ta komandu 9 yaka kopiyuye rezultat obchislennya v R 0 Primitkitim ne menshe ochevidno sho programa zi skinchennoyi kilkosti komand mozhe vikoristati lishe skinchennu kilkist registriv v teoriyi algoritmiv nul prijnyato vklyuchati do mnozhini naturalnih chisel PosilannyaCya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno berezen 2020