圖靈機與模式

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.