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

Машина з натуральночисельними регістрами, – ще одна модель для теорії алгоритмів. Не така відома, як машина Тюрінга, зате (як на мене) для неї легше складати алгоритми.

Але складати алгоритми на папірці не цікаво, тому я написав маленьке середовище, яке допомагає нам складати і перевіряти алгоритми. Ось як воно виглядає:

Зкачати можна звідси (213Кб Rar)

А ось довідка до нього:

// Дві похилі риски (як на початку цього рядка) задають коментар
//На початку рядка можна описати мітку на цей рядок записавши
// ідентифікатор мітки (послідовність букв і цифр) і закриваючу дужку.
// Система має 100 регістрів (від 0 до 99).
//Їх вміст можна побачити зправа.
// Всі значення регістрів - цілі числа від 0 до 65 535.
// Система має чотири команди :
// Z(номер_регістру - встановлює
//значення регістру в нуль.
// S(номер_регістру - збільшує
//значення регістру на одиницю
// T(номер_регістру1,номер_регістру2 -
// копіює значення регістру 1 в регістр 2
// J(номер_регістру1,номер_регістру2, ідентифікатор мітки
// - якщо регістри 1 і 2 мають однакові значення,
// то перейти до команди з міткою заданою
//в третьому параметрі. Інакше перейде до наступної команди.
// Команда якої нема в теорії, але вона
//дуже потрібна на практиці - ввід.
// I(номер_регістру - призупиняє роботу,
//щоб попросити користувача ввести дані в регістр
// При переході на мітку якої не існує,
//або після виконання останньої команди програма
зупиняється.
//Зайві пропуски будуть викликати помилки в роботі.
//Кожна команда знаходиться в новому рядку
//Важливо зауважити що закриваюча дужка
//Відділяє мітку від команди, тому не закривайте дужки

А це приклад програми, яка шукає модуль різниці двох чисел. Як бачимо все дуже просто 🙂

//Модуль різниці

I(0//Ввід
I(1
J(0,1,zero//Якщо числа рівні, то різниця - нуль
T(0,10// Копія даних
T(1,11

loop)S(0//Збільшуємо перше
S(2//Збільшуємо лічильник
J(0,1,min1//Якщо після збільшення перше стало рівне 
//другому, то воно менше
J(2,1,min2//Якщо лічильник рівний другому числу, то //вже нема сенсу його шукати
J(0,0,loop

zero)Z(0//Різниця - нуль
J(0,0,exit

//Якщо перше менше, то міняємо перше і друге місцями
min1)T(10,1
T(11,0
J(0,0,sub

//Інакше все робим як було
min2)T(10,0
T(11,1

//Тепер маємо два числа в 0 і 1 регістрах
//При чому перше строго більше ніж друге
//Тому просто їх віднімаємо
//Принцип: z=x-y => x=y+z (знайти z таке що x=y+z)
sub)Z(2
loop2)J(0,1,res
S(1
S(2
J(0,0,loop2

res)T(2,0//Результат має міститись в нульовому регістрі

Advertisements