Машины Тьюринга для уравнения с модулем

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. Двигайтесь вправо, пока не найдете 0 или 1, принадлежащие X (если вы найдете Y, пропустите ниже). Введите состояние X1, если 1 и X0 равны 0. Напишите W на ленте и переместитесь вправо к первым 0 или 1 после Y. Если вы нашли Y перед 0 или 1, то скопируйте V в начало ленты, затем запишите пробелы над всем остальным и остановись-прими.
3. Если в состоянии X0 и вы видите 0, или если вы находитесь в X1, и вы видите 1, введите состояние Z0. В противном случае введите состояние Z1.
4. Запишите W на ленту и переместитесь вправо к первой пустой ячейке после V.
5. Напишите 0, если в Z0, или 1, если в Z1.
6. Вернитесь к началу ленты и повторяйте процесс, пока не найдете Y первым на шаге 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.