将两位二进制数相加的图灵机

Question

嘿，正如标题所说，我正在尝试创建一个图灵机，它将 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

Answer 1

你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
```
)。此时，机器将永远循环或崩溃，具体取决于您的实现的具体情况，因为它将读取未初始化的磁带。

虽然它可能看起来像机器添加了

和

来获得

，但实际上它只是随意地洗牌

和

。

实际添加的 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 位数字。

Answer 2

您可以在将相同幂的最低有效位配对在一起的解决方案和为每个可能的输入创建状态的解决方案之间采取中间立场：

为左操作数的四个可能值中的每一个定义一个状态。使用该状态更新第二个操作数以成为最终的和。

这是一个可能的转换表：

状态	阅读	写	摇头	下一个状态
开始	x	_	对	val0
val0	0	_	对	val0
val0	1	_	对	val1
val0	x	_	对	停下来
val1	0	_	对	添加1
val1	1	_	对	添加11
val1	x	_	对	添加01
添加1	x	_	对	添加1
添加11	x	_	对	添加11
添加01	x	_	对	添加01
添加1	_ 或 0	1	左	停下来
添加1	1	0	左	添加1
添加01	0 或 1		对	添加1
添加11	0	1	对	添加1
添加11	1		对	添加3
添加3	0	1	左	添加1
添加3	1	0	左	添加2
添加2	1		左	添加1

用这个片段尝试一下：

createTuring({
    transitions: [
        { state: "start", read: "x",  write: "_", move: "R", nextState: "val0"  },
        { state: "val0",  read: "0",  write: "_", move: "R", nextState: "val0"  },
        { state: "val0",  read: "1",  write: "_", move: "R", nextState: "val1"  },
        { state: "val0",  read: "x",  write: "_", move: "R", nextState: "halt"  },
        { state: "val1",  read: "0",  write: "_", move: "R", nextState: "add1"  },
        { state: "val1",  read: "1",  write: "_", move: "R", nextState: "add11" },
        { state: "val1",  read: "x",  write: "_", move: "R", nextState: "add01" },
        { state: "add1",  read: "x",  write: "_", move: "R", nextState: "add1"  },
        { state: "add11", read: "x",  write: "_", move: "R", nextState: "add11" },
        { state: "add01", read: "x",  write: "_", move: "R", nextState: "add01" },
        { state: "add1",  read: "_0", write: "1", move: "L", nextState: "halt"  },
        { state: "add1",  read: "1",  write: "0", move: "L", nextState: "add1"  },
        { state: "add01", read: "01",             move: "R", nextState: "add1"  },
        { state: "add11", read: "0",  write: "1", move: "R", nextState: "add1"  },
        { state: "add11", read: "1",              move: "R", nextState: "add3"  },
        { state: "add3",  read: "0",  write: "1", move: "L", nextState: "add1"  },
        { state: "add3",  read: "1",  write: "0", move: "L", nextState: "add2"  },
        { state: "add2",  read: "1",              move: "L", nextState: "add1"  },
    ],
    initState: "start",
    tape: "x10x01",
});

<script src="https://trincot.github.io/turing.js"></script>

将两位二进制数相加的图灵机

问题描述投票：0回答：2

2个回答

最新问题

将两位二进制数相加的图灵机

问题描述 投票：0回答：2

2个回答

最新问题

问题描述投票：0回答：2