Ejemplo de Programa de Máquina de Turing
Juan Chamero, Editor Jefe de aunmas.com
Revisado y actualizado al Junio del 2008


Sea sumar dos números, por ejemplo, 2 + 3. Debemos representar esos números sobre una dimensión –la cinta- y en el sistema más elemental posible: el “unario”:

2 reprsentado como 11
3 representado como 111
y como debemos ubicarlos sobre una cinta, necesitamos al menos dos símbolos, el 1 y un símbolo que actúe como separador, eligiendo para ello el 0. Luego sobre la cinta esa cadena de datos aparecerá así:

01101110

Vamos pues a diseñar una máquina de 4 estados y que en 5 “pasos de programa” realice el cómputo requerido:

• Paso 1: [1,0,0,D,2]
• Paso 2: [2,0,0,D,3]
• Paso 3: [2,1,1,D,2]
• Paso 4: [3,0,b,I,4]
• Paso 5: [4,0,1,D,2]

Para comprender mejor cómo opera cada paso presentamos esa misma secuencia de 5-uplas en la tabla siguiente donde:



E: estado inicial
g: símbolo grabado
m: movimiento elemental: D, derecha, I, izquierda
E’: estado posterior


Si usted “ejecuta” éste programa verá que realiza satisfactoriamente el cómputo programado, quedando: 0111110