Máquina de Turing para complemento a 1 y complemento a 2

Requisito previo: máquina de Turing , complemento de 1 y 2 de un número binario 
 

Problema-1:

Dibuja una máquina de Turing para encontrar el complemento a 1 de un número binario. 

El complemento a 1 de un número binario es otro número binario obtenido alternando todos los bits en él, es decir, transformando el bit 0 en 1 y el bit 1 en 0. 

Ejemplo: 

Acercarse: 

1. Escaneando la string de entrada de izquierda a derecha
2. Convertir 1 en 0
3. Convertir 0 en 1
4. Mueva la cabeza al inicio cuando se alcance el ESPACIO EN BLANCO.

Pasos: 

• Paso 1. Convierta todos los 0 en 1 y todos los 1 en 0 y vaya a la derecha si encuentra B, vaya a la izquierda. 
• Paso 2. Luego ignore los 0 y los 1 y vaya a la izquierda y si B encuentra, vaya a la derecha
• Paso 3. Detenga la máquina. 
   

Aquí, q0 muestra el estado inicial y q1 muestra el estado de transición y q2 muestra el estado final. 
Y 0, 1 son las variables utilizadas y R, L muestra derecha e izquierda. 

Explicación: 

• Indique q0 reemplace ‘1’ con ‘0’ y ‘0’ con ‘1’ y muévase a la derecha.
• Cuando llegue a BLANCO, muévase hacia la izquierda.
• Usando el estado ‘q2’ llegamos al inicio de la string.
• Cuando llegue a BLANK muévase hacia la derecha y llegue al estado final q2. 

Problema-2:

Dibuja una máquina de Turing para encontrar el complemento a 2 de un número binario. 

El complemento a 2 de un número binario es 1 sumado al complemento a 1 del número binario. 

Ejemplo: 

Acercarse: 

1. Escaneando la string de entrada de derecha a izquierda
2. Pase todos los ‘0’ consecutivos
3. Para el primer ‘1’ que viene, no hagas nada
4. Después de eso, convertir 1 en 0 y convertir 0 en 1
5. Deténgase cuando llegue a BLANCO.

Pasos: 

• Paso 1. Primero ignore todos los 0 y 1 y vaya a la derecha y luego, si encuentra B, vaya a la izquierda. 
• Paso 2. Luego ignore todos los 0 y vaya a la izquierda, si encuentra 1, vaya a la izquierda. 
• Paso 3. Convierta todos los 0 en 1 y todos los 1 en 0 y vaya a la izquierda y si encuentra B, vaya a la derecha y detenga la máquina. 
   

Aquí, q0 muestra el estado inicial y q1 y q2 muestran el estado de transición y q3 muestra el estado final. 
Y 0, 1 son las variables utilizadas y R, L muestra derecha e izquierda. 

Explicación: 

• Usando el estado ‘q0’ llegamos al final de la string.
• Cuando llegue a BLANCO, muévase hacia la izquierda.
• Usando el estado ‘q1’ pasamos todos los 0 y nos movemos a la izquierda primero se encuentra 1.
• Pase el sencillo ‘1’ y muévase a la izquierda.
• Usando el estado ‘q2’ complementamos cada dígito y nos movemos hacia la izquierda.
• Cuando llegue a BLANK muévase hacia la derecha y llegue al estado final q2.