乗算およびモジュールチューリングマシン

Question

おそらくわずかに最適化される可能性がありますが、それはトリックを行います：

仮定 - 入力は、2つのバイナリ数（導入0であるため、0の代わりに0の代わりに01と00の代わりに01）の（_）で構成されています（_）。結果は、x * y mod 4を表すリーディングのあるバイナリ番号です。

トランジションテーブル（状態current_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 2番目の数字の右に移動します（および終了-Xを追加） -
2最初の結果ゼロを書き込みます
3 2番目の結果ゼロを書き込みます
4 xに移動する（左に行く）
5最初の数の右に移動する（左に進む）
6右の数字を1つ減らします
7減少 - 今コピー番号 - 右番号の左桁に移動します
8右番号の左桁を読み取ります
9右番号の右桁を読み取ります
右番号の10右桁は1でした - 結果の右に移動して増分
11増分結果
12 xに移動します
13右番号の右桁を読み取るために移動します
14結果の左桁に移動して増分します
15増分右番号（注 - mod 4なので、私たちはただひっくり返します）
16左の数値を減らしようとしたとき - 右桁は0でした - 00かどうかを確認しますか？
17左の数を2回減少させましたが、これで合計-1に増加しました
18増加結果の左桁が0だったとき - キャリーオーバー
19クリーンアップ