Máquina de multiplicación y módulo de turing

Question

Necesito ayuda para diseñar una máquina Turing que calcule lo siguiente f(x,y) = x*y mod 4. cómo abordar este problema en la base binaria donde $x$ y $y$ ¿Tienes dos bits?

Answer 1

Probablemente podría estar ligeramente optimizado, pero hace el truco:

Asunción: la entrada consiste (únicamente) de dos números binarios (con 01, entonces 01 en lugar de 1 y 00 en lugar de 0), separados por un símbolo en blanco (_). El resultado es un número binario con liderazgo, que representa x * y mod 4.

Tabla de transición (estado actual_symbol new_symbol Move_direction new_state):

0 0 0 r 0
0 1 1 r 0
0 _ _ r 1
1 0 0 r 1
1 1 1 r 1
1 _ x r 2
2 _ 0 r 3 
3 _ 0 l 4
4 0 0 l 4
4 x x l 5
5 0 0 l 5
5 1 1 l 5
5 x x l 5
5 _ _ l 6
6 1 0 r 7
6 0 0 l 16
7 0 0 r 7
7 1 1 r 7
7 _ _ r 7
7 x x l 8
8 0 0 l 9
8 1 1 r 10
9 0 0 l 5
9 1 1 r 14
10 x x r 10
10 0 0 r 11
10 1 1 r 11
11 0 1 l 12
11 1 0 l 18
12 0 0 l 12
12 1 1 l 12
12 x x l 13
13 0 0 l 9
13 1 1 l 9
14 0 0 r 14
14 1 1 r 14
14 x x r 15
15 0 1 r 5
15 1 0 r 5
16 0 _ r 19
16 1 0 r 17
17 0 1 r 7
18 0 1 l 12
18 1 0 l 12
19 0 _ r 19
19 1 _ r 19
19 _ _ r 19
19 x _ r halt

Descripción del estado aproximado:

• 0 Mover a la derecha del primer número (yendo a la derecha)
• 1 Mover a la derecha del segundo número (y terminar - Agregar x) -
• 2 Escribir el primer resultado cero
• 3 Escribir el segundo resultado cero
• 4 Muévete a X (yendo a la izquierda)
• 5 Mover a la derecha del primer número (ir a la izquierda)
• 6 Número derecho de disminución por uno
• 7 Decremento - Ahora número de copia - Mueva al dígito izquierdo del número derecho
• 8 Lea el dígito izquierdo del número derecho
• 9 Lea el dígito correcto del número correcto
• 10 El dígito derecho del número derecho fue 1: pasar a la derecha de resultado a un incremento
• 11 Resultado de incremento
• 12 Mover a X
• 13 Mover para leer el dígito derecho del número correcto
• 14 Mover al dígito de la izquierda del resultado al incremento
• 15 Número derecho de incremento (nota: ya que es el mod 4, solo estamos volteando)
• 16 Cuando se intentó disminuir el número de izquierda: el dígito derecho era 0 - ¿verifique si 00?
• 17 Hemos disminuido el número de izquierda por 2, ahora incrementado al total -1
• 18 Al incrementar el resultado izquierdo, el dígito era 0 - arrastrado
• 19 limpieza