AúnMás.com - Enciclopedia Latinoamericana

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