turing-machines - 2 つの数値を加算するチューリング マシン

Question

# で区切られた 2 進数の合計を計算するチューリング マシンを作成するにはどうすればよいですか。111#101B、B は空白を表す? 結果はテープの最後に書き込むことができます。

Answer 1

1. 両方の 2 進数を単項に変換するチューリング マシンを作成します (その間の空白を維持します)。
2. 空白を 1 に置き換えるチューリング マシンを書き、末尾の数字を切り落とします。
3. 単数を 2 進数に変換するチューリング マシンを作成します。
4. それらの 3 台のマシンを連結します。