Maquinas Turing

Esta entrada es para laboratorio de lenguajes de programación.

Una maquina de estado finito (o automata finito que es un modelo matemático que hace cómputos automaticamente de una entrada para dar una salida) tiene una memoria interna del cual recuerda que estado se encuentra por lo tanto, se dice que es primitiva.

Cuando permitimos una memoria externa en la una maquina pueda leer y escribir, son definidas como maquinas mas potentes o poderosas. Otra mejora es si se permite que se escane una cadena de entrada en alguna dirección y que altere dicha entrada.

Podemos definir las clases de maquinas que aceptan lenguajes libres de contexto, lenguajes sensibles al contexto y lenguajes generados por gramáticas de estructura de frases.

Maquinas Turing

Las maquinas turing son una importante tipos de maquinas. igual que las maquinas de estado finito, siempre guarda un estado particular. Se dice que la cadena de entrada a una maquina Turing es una cinta que es infinita en ambas direcciones.

Una maquina de este tipo, lee carácter por carácter y después de cada leída, la maquina se detiene o hace una de las funciones, ninguna o todas: altera el carácter, se mueve a la izquierda o a la derecha, cambia el estado, entonces se puede cambiar la cadena de entrada.

Una maquina turing T de aceptación una cadena a si, se alimenta a a T, T se detiene en un estado de aceptación.

Esto se puede demostrar que un Lenguaje L (o sea, un lenguaje variable) se genera por una gramática de estructura de frases si y solo si existe una maquina Turing que acepte a L.

La verdadera importancia de estas maquinas turing es que cualquier función que se puede hacer en una computadora, se debe de calcular en una maquina Turing, a esto se le llama hipotesis de Turing o tesis de Church. nos dice que una maquina de Turing es como una abstracción de una computadora digital.

Entonces podemos decir que un algoritmo es una maquina de Turing que, dada una cadena de entrada, en algún momento se detiene.

Bibliografia:
MATEMATICAS DISCRETAS. Sexta edición.
Johnsonbaugh, Richard
PEARSON EDUCACION, México, 2005
Área: Universitarios.


PD. es el libro que utilizamos en la materia de Mates discretas, la pagina donde viene esta información es en la 537. Lo pueden conseguir en google books. en este link


En este video podemos  ver una maquina turing en funcionamiento.



Espero que mi explicación les sirva, si tienen algún comentario acerca de esta entrada, espero me digan ya que estoy abierto a cualquier error.