Máquina de Turing para la adición

Requisito previo: máquina de Turing 
Un número se representa en formato binario en diferentes autómatas finitos. Por ejemplo, 5 se representa como 101. Sin embargo, en el caso de la suma utilizando una máquina de Turing, se sigue el formato unario. En formato unario, un número se representa ya sea por ceros o por unos. Por ejemplo, 5 estará representado por una secuencia de cinco ceros o cinco unos: 5 = 1 1 1 1 1 o 5 = 0 0 0 0 0. Usemos ceros para la representación. 

Para sumar 2 números usando una máquina de Turing, ambos números se dan como entrada a la máquina de Turing separados por una «c». 

Ejemplos: (2 + 3) se darán como 0 0 c 0 0 0: 
 

Input  :  0 0 c 0 0 0    // 2 + 3
Output :  0 0 0 0 0      // 5

Input  :  0 0 0 0 c 0 0 0  // 4 + 3
Output :  0 0 0 0 0 0 0    // 7

Enfoque utilizado: 
convierta un 0 en el primer número en X y luego recorra toda la entrada y convierta el primer espacio en blanco encontrado en 0. Luego muévase hacia la izquierda ignorando todos los 0 y «c». Llegue a la posición justo al lado de X, y repita el mismo procedimiento hasta que obtenga una «c» en lugar de X al regresar. Convierta la c en un espacio en blanco y se completa la suma. 

Pasos – 

Paso 1: Convierta 0 en X y vaya al paso 2. Si el símbolo es «c», conviértalo en blanco (B), muévase a la derecha y vaya al paso 6. 

Paso 2: siga ignorando los 0 y muévase hacia la derecha. Ignore «c», muévase a la derecha y vaya al paso 3. 

Paso 3: siga ignorando los 0 y muévase hacia la derecha. Convierta un espacio en blanco (B) en 0, muévase hacia la izquierda y vaya al paso 4. 

Paso 4: siga ignorando los 0 y muévase hacia la izquierda. Ignore «c», muévase a la izquierda y vaya al paso 3. 

Paso 5: siga ignorando los 0 y muévase hacia la izquierda. Ignore una X, muévase a la derecha y vaya al paso 1. 

Paso 6: Fin.