Construya la máquina de Turing para incrementar el número binario en 1

Prerrequisito: Máquina de Turing

Tarea:
Tenemos que diseñar una máquina de Turing para incrementar el número binario en 1.

Ejemplos –

Input: 10111
Output: 11000

Input: 1000
Output: 1001

Input: 10101011
Output: 10101100

Análisis:
de los tres ejemplos anteriores, podemos obtener dos condiciones:

• Cuando el dígito más a la derecha es 0:
  Aquí podemos ver que cuando agregamos algo a un número binario que tiene 0 como su dígito más a la derecha, entonces el dígito más a la derecha del número binario cambia, es decir, si el dígito más a la derecha es 0, cambiará a 1 y viceversa. viceversa, mientras que todos los demás dígitos permanecen iguales y nuestra máquina se detendrá cuando obtengamos Blank (B).
• Cuando el dígito más a la derecha es 1:
  aquí podemos ver que cuando agregamos algo a un número binario que tiene 1 como su dígito más a la derecha, todos los 1 cambian a 0 hasta que obtenemos un 0, y el 0 que obtenemos cambiará a 1 mientras todos los demás dígitos después de eso permanecerán iguales y nuestra máquina se detendrá cuando obtengamos Blank (B). Supongamos que no tenemos ningún 0 en una string, por ejemplo 1111, luego nos movemos hacia la izquierda hasta que obtengamos un espacio en blanco (B) que cambia todos los 1 a 0 y cambiamos este espacio en blanco (B) a 1, y nuestra máquina se detiene.

Acercarse :

1. Tenemos que escanear el elemento de derecha a izquierda. Al principio, nuestro puntero está en el extremo izquierdo. Por lo tanto, tenemos que desplazar el puntero hacia el lado más a la derecha.
2. Para desplazar el puntero hacia el extremo derecho, normalmente omitimos todos los 0 y 1 hasta que obtengamos un espacio en blanco (B).
3. Después de este paso, ahora podemos mover el puntero de izquierda a derecha.
4. Si obtenemos el primer dígito 1, cambiamos todos los 1 por 0 hasta que obtenemos un 0 y cambiamos este 0 por 1. Después de esto, todos los dígitos permanecen iguales y nuestra máquina se detiene en Blank (B).
5. Si obtenemos el primer dígito 1, entonces surge una condición de que no obtengamos ningún 0, por ejemplo, 1111, luego nos movemos hacia la izquierda hasta que obtengamos un espacio en blanco (B) cambiando todos los 1 a 0 y cambiamos este espacio en blanco (B) a 1, y nuestra máquina se detiene.
6. Si obtenemos el primer dígito como 0, entonces tenemos que cambiar 0 como 1 y después de eso, todos los dígitos permanecen iguales y nuestra máquina se detendrá en Blank (B).