如何构建图灵机来计算输入X$Y*给定的 2 个二进制数字的总和？
例如，假设X = 3和Y = 5。机器的输入将#011$101*#。最终的状态应该是#1000#.
我们可以假设X和Y具有相同的位长度。
你需要实现一个完整的加法器。这个问题可能是家庭作业，所以我将提供一个高层次的概述。图灵机M具有特殊的状态Q(xyc)x,y ∈ {0,1,U}和c ∈ {0,1}。状态Q(xyc)表示第 i 位X是x，第 i 位Y是y，进位是c。符号U表示相关输入的第 i位未知。y ∈ {0,1}无效的状态Q(Uyc)因为如果第 i位Y已知，则已知第 i位X。算法是这样的：
M的初始状态是Q(UU0)。- 假设添加了第 i位
X和Y，并且进位c。然后M处于状态Q(UUc).如果i大于X和Y中的位数，请转到步骤 (6(。由于在步骤(3(和(4(中覆盖了最低有效输入位，因此很容易检测到这种情况。 - 找到
X的最低有效位x，用$覆盖x并转换为状态Q(xUc)。 - 找到
Y的最低有效位y，用*覆盖y并转换为状态Q(xyc)。 - 在磁带末尾写下适当的总和，过渡到状态
Q(UUd)，其中d是新的进位，然后转到步骤 (2(。这些值由上面链接中的真值表给出。 - 如果
c = 1，请在磁带末尾写入c。 - 将计算值的反面复制到磁带的开头。清除剩余的磁带。
请注意，输出以相反的顺序构造，因此必须在步骤 (7( 中反转。其余工作包括用于遍历/操作磁带的写入状态和转换。