Maquinas de turing

INSTITUTO TECNOLÓGICO SUPERIOR DE VALLADOLID[pic 1][pic 2]

Asignatura:

Lenguajes Automatas

Docente:

Ing. Antonia G. Castillo Coronado

Carrera:

Ing. En sistemas Computacionales

Alumno:

Eduardo Josue Pool Nah

   Francisco javier panti kumul

  German azael nuñez lopez

Actividad:

Fehca de entrega:

Lunes 09 Noviembre 2015

Contenido

INTRODUCCION        

¿Qué es una Máquina de Turing?        

Antecedentes        

Funcionamiento        

Representación gráfica de una MT        

Lenguajes        

Lenguajes regulares:        

Lenguaje recursivamente enumerable:        

Lenguajes Libres de contexto:        

Tipos de máquinas de Turing        

∙        Máquina de Turing Multicinta        

∙        Máquina de Turing No Determinista        

∙        Máquina de Turing Multidimensional        

∙        Máquina de Turing con Múltiples Cabezales        

∙        Máquina de Turing Offline        

∙        Máquina de Turing con movimiento "stay" o "esperar"        

∙        Máquina de Turing con cinta infinita a ambos lados        

∙        Máquina de Turing con cinta multipista        

∙        Máquinas de Turing multidimensionales        

∙        Máquina de Turing Cuántica        

Conclusión        

INTRODUCCION

El tema del siguiente documento trata sobre las famosas máquinas de Turing. El objetivo de esta documentación es entender de la mejor manera el tema, saber que es las Máquinas de Turing, conocer los clasificación así como su funcionamiento, y para poder llevar a cabo el objetivo tendremos la explicación del concepto Máquinas de Turing así como los clasificación de máquinas que fueron creadas de igual manera una explicación concreta para entender mejor cada tipo, como funciona las máquinas, entre otros puntos.

¿Qué es una Máquina de Turing?

Una máquina de Turing es un autómata que consta de una cabeza lectora y una cinta infinita en la que la cabeza puede leer símbolos, borrarlos, escribirlos y moverse a la derecha o a la izquierda. Por supuesto también  consta de una función de estado que determinará los cambios de un estado a otro que se deben producir en función de las instrucciones que reciba.

Antecedentes

El matemático ingles Alan Turing definido por primera vez  este tema como una maquina automática en el año de 1936, en una revista. Y señalo que la máquina de Turing no está diseñada para una tecnología de computación. Si no como un dispositivo que representa una máquina de computación. Este ayuda a los científicos a entender los límites del cálculo mecánico.  

Turing dio una definición en un experimento en su ensayo en 1948 “Maquinas inteligentes” escribió que la máquina de Turing, es mejor llamada una máquina de computación  lógica.

Funcionamiento

La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:

• Avanzar el cabezal lector/escritor hacia la derecha. 

• Avanzar el cabezal lector/escritor hacia la izquierda. 

[pic 3]

Representación gráfica de una MT

En forma similar a las demás máquinas abstractas, una Máquina de Turing puede representarse gráficamente a través de los llamados Diagramas finitos o de transición. Un diagrama de transición está formado por un conjunto de nodos que corresponden a los estados de la MT. La transición δ(q,a)=(p,b,D)se representa así:

[pic 4]

Según esto, tenemos para un diagrama de transición los siguientes elementos:

• Estados, representados por vértices: q, p
• El estado inicial de la máquina es aquel representado por una arista sin origen. El estado final o de aceptación está representado por una doble arista. 
• Transición entre estados, representada por una arista dirigida: (a/b, D): el primer término (a) indica el símbolo leído en el cabezal; el segundo término (b) indica el símbolo que el cabezal va a escribir. El último término es la indicación del siguiente movimiento del cabezal: derecha (D o R, por la palabra inglesa Right) o izquierda (I o L, de Left).

Lenguajes

El lenguaje utilizado en las máquinas de Turing, son las siguientes:

Lenguajes regulares: gramáticas de tipo 3 formales que definen un lenguaje describiendo como se pueden generar las cadenas de lenguaje. Estos son reconocidos por un autómata finito. Son las más restrictivas. Y este contiene un símbolo terminal y símbolo no y terminal.

...