Diagrama de la máquina de Turing, un problema resuelto

Question

El siguiente diagrama Obtiene un número binario $x$ y producir $x+1$ . completarlo:

la solución del libro dice que la primera línea es la respuesta. ¿alguna pista o idea para completar esta TM?

Answer 1

La rama inferior se toma si la entrada termina en $\ldots 1$ . En ese caso, queremos sustituir el $\ldots 011\ldots 1$ con $\ldots 100\ldots 0$ (o excepcionalmente $B11\ldots 1$ con $100\ldots 0$ ). Por lo tanto, mientras leamos $1$ debemos escribir $0$ y se mueve a la izquierda; sólo cuando leemos $0$ debemos escribir $1$ , muévete a la izquierda, y procede a buscar el extremo izquierdo (como $q_2$ hace)