turing-machines

Turing machines for equation with modulo


I'm required to create a touring machine for

Z =(Xi + Ki)mod 2

but I'm completely lost in terms of creating a Turing machine for a modulo of 2. X and K are binary inputs where i is the length of the string. The input is given as such where:

XYK

the Y just acts as a separator for binary strings X and K which could vary in length. The problem I'm having now is regarding the modulo part of the equation. How do i begin with mod 2 and what I'm supposed to look out for?


Solution

  • Based on this I think what you are asking for is Z such that Z_i = X_i + Y_i (mod 2):

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

    Given this and an input tape like BXX...XY...KK...KBB... where B is blank, XX...X is an i-digit binary number, Y is a separator and KK...K is another i-digit binary number, the problem is easy:

    1. Write a new separator V to the first non-blank cell after the input. Make sure you can distinguish it from X, Y, K. Return to the beginning of the tape.
    2. Move right until you find a 0 or 1 belonging to X (if you find Y, skip below). Enter state X1 if 1 and X0 of 0. Write W on the tape and move right to the first 0 or 1 after Y. If you found Y before a 0 or 1, then copy V to the front of the tape, then write blanks over everything else and halt-accept.
    3. If in state X0 and you see a 0, or if you're in X1 and you see a 1, enter state Z0. Otherwise, enter state Z1.
    4. Write a W to the tape and move right to the first blank cell after V.
    5. Write 0 if in Z0, or 1 if in Z1.
    6. Move back to the beginning of the tape and repeat the process until you find Y first in step 2.

    Example: 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.