嘿，正如标题所说，我正试图创建一个添加2个2位数二进制数的图灵机。
到目前为止，我设法使它适用于10+01的情况，但我不能使它适用所有的数字组合。有人能帮忙吗？到目前为止，这是我的代码。
输入格式为X NUM1 NUM2 X NUM3 NUM4(x10x01(:
State Read Write Direction NextState
0 X X R 0
0 1 1 R 0
0 0 1 L 1
1 X 0 L 1
1 0 0 L 1
1 1 0 L 2
2 X 0 R 2
2 0 0 R 2
2 1 1 R 0
3 _ _ N HALT
您TM执行以下操作：
- 状态0：向右移动，直到读取0，然后写入1，向左移动，进入状态1
- 状态1：向左移动，直到我们读到1，然后写0，向右移动，进入状态2
- 状态2：向右移动，直到我们读到1，向右移动并转到状态0
- 状态3(从未达到(：停止
这个逻辑似乎没有添加任何内容。在输入x10x01上，它将：
- 磁带：
x10x01，状态0，磁头位于位置1(x(。向右移动，直到我们读取0，写入1，向左移动并转到状态1 - 磁带：
x11x01，状态1，磁头位于位置2(1(。向左移动，直到我们读到1，然后写0，向右移动，进入状态2 - 磁带：
x01x01，状态2，磁头位于位置3(1(。向右移动，直到我们读到1，向右移动并转到状态0 - 磁带：
x01x01，状态0，磁头位于位置4(x( - 磁带：
x01x11，状态1，磁头位于位置4(x( - 磁带：
x00x11，状态2，磁头位于位置4(x( - 磁带：
x00x11，状态0，磁头位于位置6(1(。此时，机器将永远循环或崩溃，这取决于实现的具体情况，因为它将读取未初始化的磁带
虽然机器添加了01和10以获得11，但实际上它只是随意地打乱了1和0。
实际添加的TM需要比您的机器多做一些事情。具体而言：
- 找到两个操作数的最低有效无标记位
- 标记它们
- 根据它们的值，确定一位结果和一位进位
- 写入结果，并将进位应用于下一个最低有效的未标记位
- 重复此步骤，直到不再有数字为止
由于您只担心两位数，因此可以跳过标记数字，只需使用其他状态来跟踪您正在使用的位。
你也可以对所有可能的输入进行硬编码(只有16个(，但这可能不符合你被分配的家庭作业的精神。
例如，要实际添加两个一位数字，您可能需要这样的算法：
- 状态0：向右移动，直到我们读到一个数字。写入0。如果数字为0，则转到状态1。如果数字为1，则转到状态2
- 状态1：向右移动，直到我们读到一个数字。如果数字为0，则转到状态3。如果数字是4，则转到状态4
- 状态2：向右移动，直到我们读到一个数字。如果数字为0，则转到状态4。如果数字是5，则转到状态5
- 状态3:写入0，停止
- 状态4：写入1，停止
- 状态5：写1，向右移动到状态3
在本例中，状态1和2跟踪第一个数字是0还是1。状态3、4和5将数字相加。状态3是当两者都为0时。状态4为1。状态5是当两者都为1时(这有进位(。
相应的TM可能看起来像这样：
State Read Write Direction NewState
0 X X R 0
0 0 0 R 1
0 1 0 R 2
1 X X R 1
1 0 0 N 3
1 1 1 N 4
2 X X R 2
2 0 0 N 4
2 1 1 N 5
3 _ 0 N Halt
4 _ 1 N Halt
5 _ 1 R 3
我将由您来决定如何将这个概念的两次迭代连接在一起，以添加两个2位数字。