Машина Маркова (52, 61)

Машина Маркова представляет собой абстрактный исполнитель алгоритмов, основанный на обработке цепей знаков (строк). Принцип работы состоит в следующем. На вход машине подаётся слово, в качестве алгоритма - набор правил (формул) подстановки, содержащих заменяемые и заменяющие фрагменты. За один шаг работы производится одна замена, правила проверяются по порядку. Если совпадений с текущим правилом несколько, выбирается самое левое. Алгоритм завершается, если ни один из заменяемых фрагментов не присутствует в слове либо если сработало одно из правил, рассматриваемых как конечные.

00.9     01.П4    02.KИП4 03.K[x] 04.П7   05.FВx  06.K{x}  07.П8   08.ИП8  09.ИПE
10.x     11.П8    12.K{x} 13.Fx=0 14.08   15.П5   16.ИП9   17.П1   18.Flg  19.K[x]
20.F10^x 21.П3    22.ИП1  23.П2   24.Сx   25.П6   26.ИП2   27.ИП7  28.-    29.Fx=0
30.72    31.ИП9   32.В^   33.Flg  34.K[x] 35.1    36.+     37.ИП5  38.-    39.F10^x
40.:     41.K[x]  42.ИП6  43.ИП8  44.Fx#0 45.50   46.Flg   47.K[x] 48.1    49.+
50.+     51.F10^x 52.x    53.ИП9  54.В^   55.ИП6  56.F10^x 57.П7   58.:    59.K[x]
60.ИП7   61.x     62.-    63.+    64.ИП8  65.ИП7  66.x     67.+    68.П9   69.С/П
70.БП    71.00    72.KИП6 73.ИП2  74.ИПE  75.:    76.K[x]  77.П2   78.Fx=0 79.26
80.KИП5  81.ИП1   82.В^   83.ИП3  84.:    85.K[x] 86.ИП3   87.x    88.-    89.П1
90.ИП3   91.ИПE   92.:    93.K[x] 94.П3   95.Fx=0 96.22    97.ИП4  98.ИП0  99.-
-0.9     -1.-     -2.Fx=0 -3.02   -4.С/П

Под правила отводится 4 регистра, под слово - 8 знакомест, алфавит - из цифр от 1 до 8. Правила помещаются в регистрах от РA в РD в формате "123,456", где "123" - заменяемый фрагмент, а "456" - замена. Количество правил заносится в Р0, начальное слово - в Р9. Номер сработавшего правила является последней цифрой регистра Р4 (от 0 до 3); если не сработало ни одно из правил, на индикаторе 0, в противном случае - обрабатываемое слово. В РE заносится 10.

Пример алгоритма (из вики). Преобразование двоичной записи числа в унарную.

Определяемся с алфавитом: для двоичных 0 и 1 пусть будет 2 и 3, а для унарной единицы - 1.

Правила: 12,211, 3,21, 2; число правил (3) записываем в Р0.

Заключительные правила отсутствуют, поэтому алгоритм исполняется до отсутствия возможности замены.

Начальным словом возьмём 101, т. е. 5 или в нашем алфавите 323, заносим в Р9. В РE - 10.

Отработка: 2123; 22113; 221121; 2212111; 22211111; 2211111; 211111; 11111; 0. Результат в Р9 - 11111.