图灵机与模式

Question

我需要创建一个巡回机

Z =(Xi + Ki)mod 2 

但我在2 X和K的模创建旅游机而言完全丧失是二进制其中i是字符串的长度。输入是这样给出的：

XYK 

Y只是充当二进制字符串X和K的分隔符，其长度可能不同。我现在遇到的问题是关于等式的模数部分。我如何开始与国防部2，我应该注意什么？

Answer 1

在此基础上我想你问的是Z-这样Z_i = X_I + Y_I（模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步

例发现Ÿ重复这个过程：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.