Maquina de turing

Una Maquina de Turing es un dispositivo que transforma un alfabeto de entrada en uno de salida después de algunos pasos, consiste en una cabeza de lectura/escritura que examina una dimensión posiblemente infinita de una cinta bidireccional dividida en cuadros cada uno de los cuales está identificado con un 0 o un 1.
Para llevar a cabo algún algoritmo la máquina inicializa en algún estado interno arbitrario. Después, entra en marcha y la máquina lee el bit que se encuentra en ese momento en su interior y ejecuta alguna operación con ese bit (lo cambia o no, dependiendo de su estado interno). A continuación se mueve hacia la derecha o hacia la izquierda, y vuelve a procesar el siguiente bit de la misma manera. Al final se para, dejando el resultado al lado izquierdo.

Siguiendo este sistema de conversión: 

s, 0 (s, 0,>)
s, 1 (s, 1,>)
s, _ (q, _ ,<)
s, ^ (s, ^,>)
q, 0 (“alto”, 1,−)
q, 1 (q, 0,<)
q, ^ (“alto”, ^,>)


Estados: s, q
Punteros: <, >, -
Estados terminales: "alto", "si", "no"
Símbolos especiales: _ , ^ 


A continuación les dejare un ejemplo que yo hice, y que mejor manera de que entiendan que con imágenes y texto, porque tal vez un programa seria un poco complejo de entender:


1.-

2.-

3.- 

4.-

5.-

6.-

7.-

Espero les sea de ayuda, estaría mejor que lo subiera en forma de vídeo pero todavía estoy en eso, aun no se muy bien como hacerlos, igual espero les sirva.


Fuente: http://campusvirtual.unex.es/cala/epistemowikia/index.php?title=La_m%C3%A1quina_de_Turing/La_teor%C3%ADa_de_la_computaci%C3%B3n_y_la_M%C3%A1quina_de_Turing

La tabla de sistema de conversión la tome de las diapositivas que nos aporto la Dra. Elisa Schaeffer