Maquinas de turing
Enviado por German Nuñez • 13 de Marzo de 2016 • Trabajos • 1.950 Palabras (8 Páginas) • 699 Visitas
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.
...