Máquina de Turing como comparador

Requisito previo: máquina de Turing

Problema: Dibuja una máquina de turing que compare dos números. Uso del formato unario para representar el número. Por ejemplo, 4 está representado por 
 

4 = 1 1 1 1  or 0 0 0 0 

Usemos uno para la representación. 

Ejemplo: 

Acercarse: 
 

1. Comparar dos números comparando el número de ‘1’.
2. Comparando ‘1’ marcándolos con ‘X’.
3. Si quedan ‘1’ a la izquierda de ‘0’, entonces el primer número es mayor.
4. Si quedan ‘1’ a la derecha de ‘0’, entonces el segundo número es mayor.
5. Si ambos ‘1’ están terminados, ambos números son iguales.

Pasos: 
 

• Paso 1: Convierta 1 en X y muévase a la derecha y vaya al paso 2. Si el símbolo es 0, ignórelo, muévase a la derecha y vaya al paso 6. 
   
• Paso 2: sigue ignorando 1 y muévete hacia la derecha. Ignore 0, mueva a la derecha y vaya al paso 3.
• Paso 3: Sigue ignorando X y muévete hacia la derecha. Ignore 1 movimiento a la izquierda y vaya al paso 4. Si se encuentra B, ignórelo, muévase a la izquierda y vaya al paso 9.
• Paso 4: Sigue ignorando X y muévete hacia la izquierda. Ignore 0, muévase a la izquierda y vaya al paso 5.
• Paso 5: Sigue ignorando 1 y muévete hacia la izquierda. Ignorar X mover a la derecha e ir al paso 1.
• Paso 6: sigue ignorando X y muévete hacia la derecha. Si se encuentra B, ignórelo, muévase hacia la izquierda y vaya al paso 8. Si se encuentra 1, ignórelo, muévase a la derecha y vaya al paso 7.
• Paso 7: detener la máquina (A < B)
• Paso 8: Detenga la máquina (A > B)
• Paso 9: Detener la máquina (A = B)

Diagrama de transición de estado: 
 

• Comparador para A < B
• Comparador para A = B
• Comparador para A > B
• Comparador universal para A < B, A = B, A > B 
   

Aquí, Q0 muestra el estado inicial y Q2, Q3, Q4, Q5 muestra el estado de transición y (A < B), (A = B) y (A > B) muestra el estado final. 0, 1 son las variables utilizadas y R, L muestra derecha e izquierda. 

Explicación: 
 

• Usando Q0, cuando se encuentre 1, conviértalo en X y vaya a la izquierda y al estado Q1. y si encuentra 0, muévase a la derecha al estado Q5.
• En el estado Q1, ignore todos los 1 y vaya a la derecha. Si encuentra 0, ignórelo y vaya a la derecha al siguiente estado Q2.
• En Q2, ignore todo X y muévase a la derecha. Si se encuentra B, detenga la ejecución y pasará al estado que muestra A > B. Si se encuentra 1, haga que X se mueva a la izquierda y a Q3.
• En el estado Q3, ignore todo X y muévase a la izquierda. Si encuentra 0, ignórelo, muévase a la izquierda a Q4.
• En Q4, ignore todo 1 y muévase a la izquierda. Si encuentra X, ignórelo, muévase a la derecha.
• En el estado Q5, ignore todo X y muévase a la derecha. Si encuentra 1, ignórelo, muévase a la derecha y detenga la máquina, dará como resultado que A < B. Y si B encuentra, muévase a la izquierda para detener la máquina, dará como resultado que A = segundo