Машина Тьюринга

Почему-то никак не удавалось найти какую-нибудь машину Тьюринга, для которой можно было бы удобно составлять программы. Пришлось набросать самому:
Машина Тьюринга

С полубесконечной лентой. Всё по канону - каретка считывает символ, берёт своё текущее состояние и на основе этой пары делает работу: пишет новый символ, меняет своё состояние и сдвигается влево/вправо или остаётся на месте. Для решения учебных задачек - типа, "заменить в строке все символы b на c" - вполне подходит.

Пусть лежит для коллекции.
Если что, там же болтаются худо-бедно работающие эмуляторы нормального алгоритма Маркова и машины с неограниченными регистрами.

Нормальный алгоритм Маркова

В общем, помыкавшись по интернету, обнаружил поразительную вещь: нечасто встречаются реализации нормального алгоритма Маркова, у которых корректно отрабатывает правило:
$0->0$$$$$$$$$$

Не знаю уж, почему так. Точнее, выяснилось, что как-то хитро себя ведет джаваскриптовская функция string.replace(), но дальше разбираться лень. Поэтому накидал свой собственный велосипед.

---

Введите начальную последовательность символов:



Нормальный алгоритм Маркова (например, a->b):
// Пример: простейший калькулятор // (сложение, вычитание, умножение натуральных чисел) // Алфавит: 1234567890+-*abcdefghioxyz^@$#? // переводим числа из унарной в десятичную систему (часть 2) z^->za o^->a a^->b b^->c c^->d d^->e e^->f f^->g g^->h h^->i i^->^o za->1z zb->2z zc->3z zd->4z ze->5z zf->6z zg->7z zh->8z zi->9z zo->0z z->. // переводим числа из десятичной в унарную систему счисления 1->0$ 2->1$ 3->2$ 4->3$ 5->4$ 6->5$ 7->6$ 8->7$ 9->8$ $0->0$$$$$$$$$$ 0-> // умножаем числа в унарной системе счисления x$->$?x x?->? x-> ?$->$? $$*$->$*x$ $*$->$ *$$->*$ *$-> ?->$ // преобразуем отрицательные числа в унарной системе счисления -$-># #$->## // убираем плюсы $+#->+ #+$->+ +-> // сокращаем пары #$-> $#-> // переводим положительные числа из унарной в десятичную систему (часть 1) ^$->^^ $->y^ y->zo // переводим отрицательные числа из унарной в десятичную систему (часть 1) ^#->^^ #->@^ @->-zo