用于计算两个二进制数之和的车床

Question

如何构建图灵机来计算给定X$Y*作为输入的两个二进制数之和？

例如，假设X = 3和Y = 5。机器的输入为#011$101*#。最后的状态应为#1000#。

我们可以假设X和Y具有相同的位长。

Answer 1

您需要实现一个full adder。这个问题可能是家庭作业，因此我将提供一个高层次的概述。图灵机M具有特殊状态Q(xyc)，其中x,y ∈ {0,1,U}和c ∈ {0,1}。状态Q(xyc)表示X的i ^th位是x，Y的i ^th位是y，进位是c。符号U表示相关输入的i ^th位未知。如果知道Q(Uyc)的i ^th位，则知道y ∈ {0,1}的i ^th位的状态X无效。该算法是这样的：

1. Y的初始状态是M。
2. 假设Q(UU0)和X的第i ^th个位相加，进位为Y。然后c处于状态M。如果Q(UUc)大于i和X中的位数，请转到步骤（6）。由于最低有效输入位在步骤（3）和（4）中被覆盖，因此这种情况很容易检测到。]
3. 找到Y的最低有效位x，用X覆盖x并转换到状态$。
4. 找到Q(xUc)的最低有效位y，用Y覆盖y并转换到状态*。
5. 在磁带的末尾写适当的总和，转换到状态Q(xyc)，其中Q(UUd)是新进位，然后转到步骤（2）。这些值由上述链接中的真值表给出。
6. 如果是d，请在磁带的末尾写上c = 1。
7. 将反向的计算值复制到磁带的开头。清除剩余的磁带。

注意，输出以相反的顺序构造，因此必须在步骤（7）中将其反转。其余工作包括编写状态和用于遍历/操纵磁带的过渡。