Maquina de Turing que Resta

Para hacer una máquina de Turing que reste por uno, usé como base el que la maestra Schaeffer nos dio como ejemplo. Usando el criterio que dice que restar es lo contrario a sumar, modifiqué dos reglas estando en el estado q, para que así al número inicial se le reste por uno. Estando en el estado q, mirando un 0, lo que sucede es: se mantiene el estado q, se imprime un 1 y nos movemos a la izquierda. En el estado q, mirando un 1, sucede: se cambia a "alto", se imprime un 0 y nos quedamos ahí. Lo anterior se aprecia en al siguiente tabla:

Primero veamos como ejemplo el mismo número que vimos en clase: 10110111 (183)

• Primero nos colocamos en el inicio › en estado s, que nos dice que nos movamos a la derecha manteniendo el ›. Nos encontramos ahora en un 1, y la regla nos dice que nos movamos a la derecha sin modificar ni el número ni el estado, misma regla para el 0. Así nos movemos, y al llegar al último uno nos encontramos con un espacio vacío. 10110111
• Cuando tenemos espacio vacío en estado s, la regla nos dice que cambiemos a estado q y ahora nos movemos a la izquierda, manteniendo el espacio. Nos encontramos en el estado q, con un 1.
• En estado q, mirando un 1, el estado ahora es "alto", se cambia el 1 por un 0 y no nos movemos.. El resultado es 10110110 (182)

Ahora usemos el siguiente ejemplo. Nuestro valor inicial es 11001000 (200)

• Al principio, actúa igual que en el anterior ejemplo. Primero nos colocamos en el inicio › en estado s, que nos dice que nos movamos a la derecha manteniendo el ›. Nos encontramos ahora en un 1, y la regla nos dice que nos movamos a la derecha sin modificar ni el número ni el estado, misma regla para el 0. Así nos movemos, y al llegar al último uno nos encontramos con un espacio vacío.   11001000
• Cuando tenemos espacio vacío en estado s, la regla nos dice que cambiemos a estado q y ahora nos movemos a la izquierda, manteniendo el espacio. Ahora nos encontramos en estado q pero con un 0.
• En estado q, mirando un 0, la regla nos dice que se mantiene el estado q, cambiamos el 0 por 1 y nos movemos a la izquierda. 11001001
• Nos encontramos con un 0 denuevo, entonces aplicamos la misma regla: se mantiene el estado q, cambiamos el 0 por 1 y nos movemos a la izquierda. 11001011
• Denuevo un 0, repetimos la regla: se mantiene el estado q, cambiamos el 0 por 1 y nos movemos a la izquierda. 11001111
• Ahora nos encontramos con un 1. Nuestra máquina de Turing aplica la regla correspondiente que dice que en estado q, mirando un 1, el estado ahora es "alto", se cambia el 1 por un 0 y no se mueve la posición. Como resultado: 11000111 (199)

Bibliografía: http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/pdf/modelos.pdf