图灵机方程与模

Question

我需要为

制作一台巡演机器

Z =(Xi + Ki)mod 2

但我完全不知道如何为 modulo 2 创建图灵机。X 和 K 是二进制输入，其中 i 是字符串的长度。输入如下：

XYK

Y 只是作为二进制字符串 X 和 K 的分隔符，它们的长度可能会有所不同。我现在遇到的问题是关于等式的 modulo 部分。我该如何开始 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位二进制数，问题很简单：

将新的分隔符 V 写入输入后的第一个非空白单元格。确保您可以将它与 X、Y、K 区分开来。Return 到磁带的开头。
向右移动，直到找到属于 X 的 0 或 1（如果找到 Y，请跳过下面）。如果 1 和 X0 为 0，则进入状态 X1。在磁带上写入 W，然后向右移动到 Y 之后的第一个 0 或 1。如果在 0 或 1 之前找到 Y，则将 V 复制到磁带的前面，然后写入空白超越一切并停止接受。
如果在状态 X0 中看到 0，或者如果在 X1 中看到 1，请进入状态 Z0。否则，进入状态Z1。
在磁带上写一个 W，然后向右移动到 V 之后的第一个空白单元格。
在Z0写0，在Z1写1
回到磁带的开头并重复该过程，直到您在第 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.

图灵机方程与模

Turing machines for equation with modulo

turing-machines