图灵机算法

Question

我正在尝试确定图灵机（仅由 0 和 1 组成，没有空格）如何识别 8 个 1 的序列。我发现的每个算法都有一个 TM 搜索不确定数量的 1 或 0，而不是特定的数字。

基本上，如果你有这盘磁带：

1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1

你怎么知道8个1代表加法，你要加0 0 0 1和0 0 0 1？

Answer 1

我认为 11111111 就像一个操作码，而 0001、0001 是该操作码的操作数。至少，这是我看到的唯一解释。

TM 可以通过使用类似的固定的、有限数量的状态来寻找固定的、有限数量的符号，每个状态的唯一目的是识别另一个预期符号已被看到。例如，这是一个识别加法并进行二进制加法的四带 TM：

|----|----|----|----|----||----|-----|-----|-----|-----|----|----|----|----|
| Q  | T1 | T2 | T3 | T4 || Q' | T1' | T2' | T3' | T4' | D1 | D2 | D3 | D4 |
|----|----|----|----|----||----|-----|-----|-----|-----|----|----|----|----|
// read the opcode /////////////////////////////////////////////////////////
| qA | 1  | x  | y  | z  || qB | 1   | x   | y   | z   | R  | S  | S  | S  |
| qB | 1  | x  | y  | z  || qC | 1   | x   | y   | z   | R  | S  | S  | S  |
| qC | 1  | x  | y  | z  || qD | 1   | x   | y   | z   | R  | S  | S  | S  |
| qD | 1  | x  | y  | z  || qE | 1   | x   | y   | z   | R  | S  | S  | S  |
| qE | 1  | x  | y  | z  || qF | 1   | x   | y   | z   | R  | S  | S  | S  |
| qF | 1  | x  | y  | z  || qG | 1   | x   | y   | z   | R  | S  | S  | S  |
| qG | 1  | x  | y  | z  || qH | 1   | x   | y   | z   | R  | S  | S  | S  |
| qH | 1  | x  | y  | z  || qI | 1   | x   | y   | z   | R  | S  | S  | S  |
// read the first addend ///////////////////////////////////////////////////
| qI | w  | x  | y  | z  || qJ | w   | w   | y   | z   | R  | R  | S  | S  |
| qJ | w  | x  | y  | z  || qK | w   | w   | y   | z   | R  | R  | S  | S  |
| qK | w  | x  | y  | z  || qL | w   | w   | y   | z   | R  | R  | S  | S  |
| qL | w  | x  | y  | z  || qM | w   | w   | y   | z   | R  | R  | S  | S  |
// read the second addend //////////////////////////////////////////////////
| qM | w  | x  | y  | z  || qN | w   | x   | w   | z   | R  | S  | R  | S  |
| qN | w  | x  | y  | z  || qO | w   | x   | w   | z   | R  | S  | R  | S  |
| qO | w  | x  | y  | z  || qP | w   | x   | w   | z   | R  | S  | R  | S  |
| qP | w  | x  | y  | z  || qQ | w   | x   | w   | z   | R  | S  | R  | S  |
// prepare the output tape /////////////////////////////////////////////////
| qQ | w  | x  | y  | z  || qR | w   | x   | y   | z   | S  | S  | S  | R  |
| qR | w  | x  | y  | z  || qS | w   | x   | y   | z   | S  | S  | S  | R  |
| qS | w  | x  | y  | z  || qT | w   | x   | y   | z   | S  | S  | S  | R  |
| qT | w  | x  | y  | z  || qU | w   | x   | y   | z   | S  | S  | S  | R  |
// handle addition when no carry ///////////////////////////////////////////
| qU | w  | 0  | 0  | z  || qU | w   | 0   | 0   | 0   | S  | L  | L  | L  |
| qU | w  | 0  | 1  | z  || qU | w   | 0   | 1   | 1   | S  | L  | L  | L  |
| qU | w  | 1  | 0  | z  || qU | w   | 1   | 0   | 1   | S  | L  | L  | L  |
| qU | w  | 1  | 1  | z  || qV | w   | 1   | 1   | 0   | S  | L  | L  | L  |
| qU | w  | B  | B  | B  || hA | w   | B   | B   | B   | S  | R  | R  | R  |
// handle addition when carry //////////////////////////////////////////////
| qV | w  | 0  | 0  | z  || qU | w   | 0   | 0   | 1   | S  | L  | L  | L  |
| qV | w  | 0  | 1  | z  || qV | w   | 0   | 1   | 0   | S  | L  | L  | L  |
| qV | w  | 1  | 0  | z  || qV | w   | 1   | 0   | 0   | S  | L  | L  | L  |
| qV | w  | 1  | 1  | z  || qV | w   | 1   | 1   | 1   | S  | L  | L  | L  |
| qV | w  | B  | B  | B  || hA | w   | B   | B   | B   | S  | R  | R  | R  |
|----|----|----|----|----||----|-----|-----|-----|-----|----|----|----|----|

图例：

问：当前状态
T1: 当前磁带符号，输入磁带
T2：当前磁带符号，草稿磁带#1
T3：当前磁带符号，草稿磁带#2
T4：当前磁带符号，输出磁带（未使用）
Q'：过渡到的状态
T1'：写入输入磁带的符号（未使用）
T2'：写入暂存磁带 #1 的符号
T3'：写入暂存磁带 #2 的符号
T4'：写入输出磁带的符号
D1：输入带头移动方向
D2：移动暂存磁带 #1 磁头的方向
D3：移动暂存磁带 #2 头的方向
D4：输出带头移动方向

惯例：

w、x、y 和 z 是变量，表示 0 或 1。使用所有这四个的转换可以被认为是用于编写十六 (2^4) 个具体转换的 shorthand 符号.
方向为 L=左，S=相同，R=右。
B为空白符号；如果增加更多的状态来辅助U和V相加就可以不用了

图灵机算法

Turing Machine algorithms

algorithm

binary

turing-machines