时间戳

首页 > 解决方案 > 图灵机添加 2 位二进制数

binary - 图灵机添加 2 位二进制数

问题描述

嘿，正如标题所说，我正在尝试创建一个添加 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

标签： binarycomputer-scienceturing-machines

解决方案

您 TM 执行以下操作：

  • 状态 0：向右移动直到我们读到 0，然后写入 1，向左移动并进入状态 1。
  • 状态 1：向左移动直到我们读到 1，然后写入 0，向右移动并进入状态 2。
  • 状态 2：向右移动直到我们读到 1，向右移动并进入状态 0。
  • 状态 3（从未达到）：停止

这个逻辑似乎没有添加任何东西。在输入x10x01时它将：

  1. 磁带：x10x01，状态 0，头在位置 1 ( x)。向右移动直到我们读到 0，写 1，向左移动并进入状态 1。
  2. 磁带：x11x01，状态 1，头部位于位置 2 ( 1)。向左移动直到我们读取到 1，然后写入 0，向右移动并进入状态 2。
  3. 胶带：x01x01，状态 2，头部位于位置 3 ( 1)。向右移动直到我们读到 1，向右移动并进入状态 0。
  4. 磁带：x01x01，状态 0，头在位置 4 ( x)。
  5. 胶带：x01x11，状态 1，头部位于位置 4 ( x)。
  6. 胶带：x00x11，状态 2，头部位于位置 4 ( x)。
  7. 磁带：x00x11，状态 0，头部位于位置 6 ( 1)。此时机器将永远循环或崩溃，具体取决于您的实现细节，因为它将读取未初始化的磁带。

虽然它看起来像是机器添加01和10获取11，但实际上它只是随意地打乱了1s 和s 。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 位数字。

推荐阅读