Машина умножения и модуля Тьюринга

Question

Возможно, может быть слегка оптимизирован, но это делает свое дело:

Предположение - Вход состоит (исключительно) двух двоичных чисел (с лидером 0, поэтому 01 вместо 1 и 00 вместо 0), разделенных пустым символом (_). Результатом является двоичное число с ведущим, представляющим x * y mod 4.

Таблица перехода (состояние curity_symbol new_symbol move_direction new_state):

0 0 0 r 0
0 1 1 r 0
0 _ _ r 1
1 0 0 r 1
1 1 1 r 1
1 _ x r 2
2 _ 0 r 3 
3 _ 0 l 4
4 0 0 l 4
4 x x l 5
5 0 0 l 5
5 1 1 l 5
5 x x l 5
5 _ _ l 6
6 1 0 r 7
6 0 0 l 16
7 0 0 r 7
7 1 1 r 7
7 _ _ r 7
7 x x l 8
8 0 0 l 9
8 1 1 r 10
9 0 0 l 5
9 1 1 r 14
10 x x r 10
10 0 0 r 11
10 1 1 r 11
11 0 1 l 12
11 1 0 l 18
12 0 0 l 12
12 1 1 l 12
12 x x l 13
13 0 0 l 9
13 1 1 l 9
14 0 0 r 14
14 1 1 r 14
14 x x r 15
15 0 1 r 5
15 1 0 r 5
16 0 _ r 19
16 1 0 r 17
17 0 1 r 7
18 0 1 l 12
18 1 0 l 12
19 0 _ r 19
19 1 _ r 19
19 _ _ r 19
19 x _ r halt

Описание грубого состояния:

0 Двигайтесь справа от первого числа (иду справа)
1 Двигайтесь справа от второго числа (и завершить - добавить x) -
2 Напишите первый результат ноль
3 Напишите второй результат нулевой
4 Переезд на Х (влево)
5 двигаться справа от первого числа (влево)
6 уменьшение правильного числа на один
7 Уменьшен - теперь номер копии - перейти к левой цифре правого номера
8 Прочитайте левую цифру правого номера
9 Прочтите правую цифру правого номера
10 правая цифра правого числа составила 1 - Двигайтесь справа от результата, чтобы увеличить
11 Результат увеличения
12 Переезд в х
13 Переезд, чтобы прочитать правую цифру правого номера
14 Перейдите в левую цифру результата, чтобы увеличить
15 Приращение правого номера (примечание - так как это мод 4, мы просто переворачиваем)
16 При попытке уменьшить левый номер - правая цифра была 0 - Проверьте, если 00?
17 Мы уменьшили левое число на 2, теперь увеличение до -1
18 При увеличении результата левого цифры составила 0 - перенос
19 Очистка