npm package: @mini_machine/core
Description: В даннном пакете реализован интерпретатор расширенной Минимашины. Пакет может быть использован в тренажерах или интерактивных пособиях по дискретной математике.
Author: t.puzanov@internet.ru
Latest version: 0.1.5

# TypeScript реализация интерпретатора расширенной минимашины

В даннном пакете реализован интерпретатор расширенной Минимашины. Пакет может быть использован в тренажерах или интерактивных пособиях по дискретной математике.   


## Определение минимашины и расширенной минимашины

### Минимашины

*Минимашина* (ММ) - абстрактный исполнитель (абстрактная вычислительная машина), дает формализацию вычислимости, очень близкую к реальным языкам программирования.

Каждая ММ имеет:
- бесконечное семейство *основных регистров* $R_0, R_1, R_2, R_3, ...$
- *командный регистр* (или регистр команд КР)
- *программу*, представляющую собой (возможно пустой) список *команд*, пронумерованных последовательными числами, начиная с 0

Регистры $R_i$ и КР предназначены для хранения натуральных чисел, и в этом смысле сильно напоминают переменные языка программирования. В любой момент времени в каждом регистре записано ровно одно натуральное число

Имеется шесть легко запоминаемых типов команд, естественно разделённых на 3 группы, описание которых приведено в следующей таблице (в ней F, G, H - основные регистры).

<table>
  <tr>
    <th colspan="2">Команды присваивания</th>
  </tr>
  <tr>
    <td width="20%">G := m</td>
    <td>
      записывает в регистр G натуральное число m и
      увеличивает содержимое регистра команд на 1 
      (т.е., ММ переходит к исполнению следующей 
      по списку команды)
    </td>
  </tr>
  <tr>
    <td width="20%">G := H</td>
    <td>
      записывает в регистр G значение, содержащееся
      в регистре H, и увеличивает содержимое регистра команд на 1
    </td>
  </tr>
  <tr>
    <th colspan="2">Арифметические команды</th>
  </tr>
  <tr>
    <td width="20%">inc G</td>
    <td> увеличивает содержимое регистра G на 1 и увеличивает содержимое регистра команд на 1 </td>
  </tr>
  <tr>
    <td width="20%">dec H</td>
    <td>
      уменьшает содержимое регистра H на 1, если 
      оно больше нуля, и увеличивает содержимое регистра команд на 1
    </td>
  </tr>
  <tr>
    <th colspan="2">Команды перехода</th>
  </tr>
  <tr>
    <td width="20%">if F=0 goto m</td>
    <td>
      если содержимое регистра F равно 0, то заносит
      в командный регистр число m, в противном случае 
      увеличивает значение командного регистра на 1
    </td>
  </tr>
  <tr>
    <td width="20%">goto m</td>
    <td>заносит в регистр команд число m</td>
  </tr>
</table>


Перед началом работы минимашины в её основные регистры заносятся некоторые исходные данные (натуральные числа), а в регистр КР заносится число 0. Минимашина работает, последовательно исполняя шаги. Шаг работы машины состоит в выполнении команды, номер которой в данный момент записан в КР в соответствии с вышеописанной инструкцией. Выполнив шаг, минимашина переходит к следующему шагу и т.д. В случае, когда в КР окажется число, не являющееся номером какой-либо команды из программы, машина завершает свою работу и останавливается. Отметим, что команды перехода могут осуществлять как переход к выполнению конкретных команд так и остановку работы машины в случае, когда команда с соответствующим номером отсутствует. Заметим, что каждая программа может изменять значения только в тех регистрах, которые явно упомянуты в её тексте. Значения в остальных регистрах она изменить не может.


### Расширенные минимашины

*Расширенные минимашины* (РММ) - это абстрактный исполнитель, отличающийся от минимашин только тем, что в программах для этих машин кроме обычных команд разрешено использовать дополнительные команды вида $H:=f(H_1,...,H_k)$, для произвольных (вообще говоря, частичных) функций $f$ (здесь $H, H_1,...,H_k$ - основные регистры). Исполнение такой команды состоит в вычислении значения $f$ на значениях регистров $H_1,...,H_k$ и помещении результата в регистр $H$ с последующим увеличением значения КР на 1. Значения всех остальных регистров расширенной машины при этом не изменяются. Если $f$ не определена на данных значениях, то считается, что вычисление значения $f$ продолжается бесконечно, и при этом, разумеется, расширенная машина, выполняющая эту команду, никогда не завершит свою работу. Легко заметить, что минимашины являются частным случаем расширенных минимашин