В даннном пакете реализован интерпретатор расширенной Минимашины. Пакет может быть использован в тренажерах или интерактивных пособиях по дискретной математике.
Минимашина (ММ) - абстрактный исполнитель (абстрактная вычислительная машина), дает формализацию вычислимости, очень близкую к реальным языкам программирования.
Каждая ММ имеет:
- бесконечное семейство основных регистров
$R_0, R_1, R_2, R_3, ...$ - командный регистр (или регистр команд КР)
- программу, представляющую собой (возможно пустой) список команд, пронумерованных последовательными числами, начиная с 0
Регистры
Имеется шесть легко запоминаемых типов команд, естественно разделённых на 3 группы, описание которых приведено в следующей таблице (в ней F, G, H - основные регистры).
| Команды присваивания | |
|---|---|
| G := m | записывает в регистр G натуральное число m и увеличивает содержимое регистра команд на 1 (т.е., ММ переходит к исполнению следующей по списку команды) |
| G := H | записывает в регистр G значение, содержащееся в регистре H, и увеличивает содержимое регистра команд на 1 |
| Арифметические команды | |
| inc G | увеличивает содержимое регистра G на 1 и увеличивает содержимое регистра команд на 1 |
| dec H | уменьшает содержимое регистра H на 1, если оно больше нуля, и увеличивает содержимое регистра команд на 1 |
| Команды перехода | |
| if F=0 goto m | если содержимое регистра F равно 0, то заносит в командный регистр число m, в противном случае увеличивает значение командного регистра на 1 |
| goto m | заносит в регистр команд число m |
Перед началом работы минимашины в её основные регистры заносятся некоторые исходные данные (натуральные числа), а в регистр КР заносится число 0. Минимашина работает, последовательно исполняя шаги. Шаг работы машины состоит в выполнении команды, номер которой в данный момент записан в КР в соответствии с вышеописанной инструкцией. Выполнив шаг, минимашина переходит к следующему шагу и т.д. В случае, когда в КР окажется число, не являющееся номером какой-либо команды из программы, машина завершает свою работу и останавливается. Отметим, что команды перехода могут осуществлять как переход к выполнению конкретных команд так и остановку работы машины в случае, когда команда с соответствующим номером отсутствует. Заметим, что каждая программа может изменять значения только в тех регистрах, которые явно упомянуты в её тексте. Значения в остальных регистрах она изменить не может.
Расширенные минимашины (РММ) - это абстрактный исполнитель, отличающийся от минимашин только тем, что в программах для этих машин кроме обычных команд разрешено использовать дополнительные команды вида