模方程图灵机

Question

我需要为

创建一台巡演机

Z =(Xi + Ki)mod 2

但是我完全迷失了创建一个以 2 为模的图灵机。X 和 K 是二进制输入，其中 i 是字符串的长度。输入如下给出：

XYK

Y 只是充当长度可能不同的二进制字符串 X 和 K 的分隔符。我现在遇到的问题是关于方程的模部分。我如何开始使用 mod 2 以及我应该注意什么？

Answer 1

基于此，我认为你要求的是 Z 使得 Z_i = X_i + Y_i (mod 2):

 (X0 X1 X2 ... Xi
+ K0 K1 K2 ... Ki)
%  2  2  2 ...  2
= Z0 Z1 Z2 ... Zi

给定这个和像 BXX...XY...KK...KBB... 这样的输入磁带，其中 B 为空白，XX...X 是 i 位二进制数，Y 是分隔符，KK.. .K是另一个i位二进制数，问题很简单：

1. 将新的分隔符 V 写入输入后的第一个非空白单元格。确保您可以将其与 X、Y、K 区分开。返回到磁带的开头。
2. 向右移动，直到找到属于 X 的 0 或 1（如果找到 Y，请跳过下面）。如果为1且X0为0，则进入状态X1。在磁带上写入W，然后向右移动到Y后面的第一个0或1。如果在0或1之前找到Y，则将V复制到磁带的前面，然后写入空白超越一切并停止接受。
3. 如果处于状态 X0 并且您看到 0，或者如果处于 X1 并且您看到 1，则进入状态 Z0。否则，进入状态Z1。
4. 在磁带上写一个 W，然后向右移动到 V 之后的第一个空白单元格。
5. 如果在 Z0 则写 0，如果在 Z1 则写 1。
6. 移回到磁带的开头并重复此过程，直到在步骤 2 中首先找到 Y。

示例：0011 + 1010

B0011Y1010BBBBB...
^

B0011Y1010VBBBB...
^                 move to the end of input, write V separator, reset head

B0011Y1010VBBBB...
 ^                move right to first 0

BW011Y1010VBBBB...
      ^           enter X0, write W, move right to first 1 after Y

BW011YW010VBBBB...
           ^      enter Z1, write W, move right to first blank after V

BW011YW010V1BBB...
^                 write 1, return to beginning, repeat

BWW11YWW10V10BB...
^                 find 0, X0, find 0, Z0, write 0, return to start, repeat


BWWW1YWWW0V100B...
^                 find 1, X1, find 1, Z0, write 0, return to start, repeat

BWWWWYWWWWV1001...
^                 find 1, X1, find 0, Z1, write 1, return to start, repeat

B1001BBBBBBBBBB...
^                 find Y, copy from after V to beginning, erase rest, halt.

Answer 2

您可以重新使用X操作数的空间来写入Z的值：

• 获取并拉出（K 操作数）输入中的最后一位数字
• 将其添加到紧邻“Y”左边的数字，但先不要写入。相反，在那里写一个“Y”，并在其右侧写下模 2 结果（替换那里的“Y”）。
• 重复直到到达输入的开头。

这是一个转换表，可以在您选择的输入上的 JavaScript 代码片段中运行。

createTuring({
    transitions: [
        { state: "start",   read: "Y01",            move: "R", nextState: "start"  },
        { state: "start",   read: "_",              move: "L", nextState: "pop"    },
        { state: "pop",     read: "0",  write: "_", move: "L", nextState: "carry0" },
        { state: "pop",     read: "1",  write: "_", move: "L", nextState: "carry1" },
        { state: "carry0",  read: "01",             move: "L", nextState: "carry0" },
        { state: "carry0",  read: "Y",              move: "L", nextState: "add0"   },
        { state: "carry1",  read: "01",             move: "L", nextState: "carry1" },
        { state: "carry1",  read: "Y",              move: "L", nextState: "add1"   },
        { state: "add0",    read: "Y",              move: "L", nextState: "add0"   },
        { state: "add0",    read: "0",  write: "Y", move: "R", nextState: "back0"  },
        { state: "add0",    read: "1",  write: "Y", move: "R", nextState: "back1"  },
        { state: "add1",    read: "Y",              move: "L", nextState: "add1"   },
        { state: "add1",    read: "0",  write: "Y", move: "R", nextState: "back1"  },
        { state: "add1",    read: "1",  write: "Y", move: "R", nextState: "back0"  },
        { state: "back0",   read: "Y",  write: "0", move: "L", nextState: "check"  },
        { state: "back1",   read: "Y",  write: "1", move: "L", nextState: "check"  },
        { state: "check",   read: "Y",              move: "L", nextState: "check"  },
        { state: "check",   read: "_",              move: "R", nextState: "cleanup"},
        { state: "check",   read: "01",             move: "R", nextState: "start"  },
        { state: "cleanup", read: "Y",  write: "_", move: "R", nextState: "halt"   },
    ],
    initState: "start",
    tape: "01001Y11100",
});

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