Doodle Maquina de Turing

En la década de los 30, el inglés Allan Turing diseñó  el modelo matemático de una máquina teórica  con un gran poder computacional, llamada máquina de Turing (M.T.)

Formalmente una máquina de Turing se define como:

MT= {Q, Σ, Γ, f, q0, b, F}

Q es el conjunto finito de estados

Σ es el alfabeto de la cadena de entrada

Γ es el alfabeto de la cinta
q0 ∈ Q es el estado inicial
b es el espacio en blanco b ∈ Γ, pero b no pertenece a Σ


F ⊂ Q es el conjunto de estados finales

f: Q × Γ→Q × Γ× {I, D}

Para el caso de la G que tiene código binario 01011 en el dodle de Google es

Q={q0,q1,q2,q3,q4,q5}

Σ = {0,1}

Γ= {0,1}

Tabla de transición para la entrada 00010 es la siguiente:

           

	símbolo
estado	0	1
q0	(q1,0,I)	-
q1	(q2,1,R)	-
q2	(q3,0,R)	-
q3	-	(q4,1,R)
q4	(q5,1,R)	-
q5	Estado final de aceptación

Su salida en el doodle es:

A continuación presento el diagrama de estados hecho en jflap

Fuente: 

García, L., Martínez, G. (2005). Máquinas de Turing. En Apuntes de teoría de autómatas y lenguajes formales. (pp. 109-126). Barcelona: Edit. Reverté.