turing-machines - 图灵机加两个数

Question

我如何创建图灵机，它将计算以#分隔的两个二进制数字的总和，例如。111#101B，其中 B 代表空白？结果可以写在磁带的末尾。

Answer 1

1. 编写一个图灵机将两个二进制数转换为一元（保持它们之间的空白）。
2. 写一个图灵机，用 1 代替空白，并从末尾砍掉一个数字。
3. 编写图灵机将一元数转换为二进制数。
4. 将这三台机器连在一起。

Answer 2

假设输入 a#(1)b 转换为 a#(1)b#(2)c#(3)BLANK

空白将填写总和。为“a”的 LSB 制作 2 个案例。为“b”的 LSB 进一步划分 2 个案例。'c' 是最初为 0 的进位位。为四种情况中的每一种情况分别制作 2 种情况，并在途中更新进位位。路径是根据“c”是 0 还是 1 来选择的。

图片显示了一个粗略的草图。

最终结果将是原始总和的反转值。你再把它反过来。用一粒盐拍照。这只是一个粗略的草图。不遵循命名法。