以二进制表示形式递增一个数字：处理进位的问题

Question

我正在从事以下项目：

设计一个执行二进制数递增操作的图灵机。假设您有一个二进制数 𝑛。最初，磁带上有符号
$
，后跟二进制数 𝑛。图灵机的头部开始定位在
$
符号上，同时图灵机处于状态𝑞₀。当磁带包含
$
符号后跟二进制值 𝑛+1，并且图灵机处于状态 𝑞_𝑓 时，图灵机必须停止。磁带上的
Δ
符号代表磁带上的空单元。

我的模型

L 为左，R 为右，N 表示头部不动：

从𝑞₀到𝑞₁：
- 如果读数为
```
$
```
  ，则保持为
```
$
```
  并将头部向右移动 (R)。
在𝑞₁（处理位）：
- 如果显示为
```
0
```
  ，则保持为
```
0
```
  并向右移动 (R)。
- 如果显示为
```
1
```
  ，则保持为
```
1
```
  并向右移动 (R)。
- 如果读数为
```
Δ
```
  ，则移动到状态𝑞₂并向左移动（L）。
在𝑞₂（增量）中：
- 如果显示为
```
0
```
  ，则会将其更改为
```
1
```
  （无进位）并转到 𝑞_𝑓（结束）。
- 如果显示为
```
1
```
  ，则会将其更改为
```
0
```
  （进位）并继续在 𝑞₂ 中向左移动 (L)。
- 如果显示为
```
$
```
  ，则会转到 𝑞₃ 并向左移动 (L)。
在𝑞₃（额外携带的处理）：
- 如果显示为
```
Δ
```
  ，则会将其更改为
```
1
```
  （开始时进位）并转到 𝑞_𝑓（结束）。
- 如果显示为
```
0
```
  ，则保持为
```
0
```
  并向左移动 (L)。
- 如果显示为
```
1
```
  ，则保持为
```
1
```
  并向左移动 (L)。
- 如果显示为
```
$
```
  ，则保持为
```
$
```
  并继续在 𝑞₃ 向左移动 (L)。
在𝑞₄（空，特殊情况）：
- 如果显示为
```
Δ
```
  ，则会将其更改为
```
1
```
  并转到 𝑞_𝑓（结束）。
最终状态𝑞_𝑓：
- 增量完成后机器停止。

问题

我被告知这个模型是错误的。最初我没有状态𝑞₄，但我添加它是为了考虑进位的特殊情况。我用几个输入对此进行了测试，但无法发现问题所在。我的错误在哪里？

Answer 1

当输入数字仅包含

数字时，例如当磁带有

$11

时，就会出现问题。在这种情况下，您的算法将正确地将所有这些数字更改为

并识别出存在进位，但会将进位写入错误的位置。对于

$11

示例，它将在磁带上以

1$00

结束该过程，而它应该是

$100

。

不是问题，但是：

当处于状态𝑞₃时，您预见它可以读取符号
```
0
```
、
```
1
```
或
```
$
```
，但这些实际上都不会发生，因为您只能通过移动到达状态𝑞₃
```
$
```
符号的左边，除了空白之外没有其他东西
```
$
```
的一侧。
状态𝑞₄无法到达（没有传入转换，也不是起始状态），因此它没有任何作用。

这是在转换表中编码的模型，该模型在 JavaScript 片段中提供给可运行的图灵机。您可以在这里运行它，看看输入如何出错

$11

。

createTuring({
    transitions: [
        { state: "q0", read: "$",              move: "R", nextState: "q1" },
        { state: "q1", read: "01",             move: "R", nextState: "q1" },
        { state: "q1", read: "Δ",              move: "L", nextState: "q2" },
        { state: "q2", read: "1",  write: "0", move: "L", nextState: "q2" },
        { state: "q2", read: "0",  write: "1",            nextState: "qf" },
        { state: "q2", read: "$",              move: "L", nextState: "q3" },
        { state: "q3", read: "$01",            move: "L", nextState: "q3" },
        { state: "q3", read: "Δ",  write: "1",            nextState: "qf" },
        { state: "q4", read: "Δ",  write: "1",            nextState: "qf" },
    ],
    initState: "q0",
    blank: "Δ",
    tape: "$11" // Example input
});

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

修复

要解决此问题，请在找到

符号的位置（不是其左侧）写入额外的进位，然后使用状态 𝑞₃ 在该位置的左侧写入新的

.

那么我们就得到了这个转换表：

createTuring({
    transitions: [
        { state: "q0", read: "$",              move: "R", nextState: "q1" },
        { state: "q1", read: "01",             move: "R", nextState: "q1" },
        { state: "q1", read: "Δ",              move: "L", nextState: "q2" },
        { state: "q2", read: "1",  write: "0", move: "L", nextState: "q2" },
        { state: "q2", read: "0",  write: "1",            nextState: "qf" },
        { state: "q2", read: "$",  write: "1", move: "L", nextState: "q3" },
        { state: "q3", read: "Δ",  write: "$",            nextState: "qf" },
    ],
    initState: "q0",
    blank: "Δ",
    tape: "$11" // Example input
});

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

您可以通过此实现尝试不同的输入，并确保它现在适用于所有有效输入。

以二进制表示形式递增一个数字：处理进位的问题

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

我的模型

问题

1个回答

修复

最新问题

以二进制表示形式递增一个数字：处理进位的问题

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

我的模型

问题

1个回答

修复

最新问题

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