Musica

Introducci´n o Propiedades b´sicas de las MT a Definici´n formal de la MT o MT como aceptadoras de lenguajes

Teor´ de Aut´matas y Lenguajes Formales ıa o Tema 8. M´quinas de Turing (I) a
Yolanda Garc´ Ruiz (UCM) ıa

April 12, 2011

Yolanda Garc´ Ruiz (UCM) ıa

Teor´ de Aut´matas y Lenguajes Formales Tema 8. M´quinas d ıa o a

Introducci´n o Propiedades b´sicas de las MT a Definici´nformal de la MT o MT como aceptadoras de lenguajes

Biograf´ ıa MT

Hasta ahora hemos visto dos tipos de aut´matas: o
Aut´matas finitos o Aut´matas a Pila o

En ambos casos hemos estudiado la capacidad de ´stos e aut´matas para reconocer lenguajes o Los AF, reconocedores de lenguajes regulares, son menos potentes que los AP, ya que ´stos ultimos reconocen un tipo e ´ de lenguajes m´s amplio,los lenguajes independientes del a contexto En este cap´ ıtulo estudiaremos otra clase de aut´matas m´s o a generales, las m´quinas de Turing y a su capacidad para reconocer lenguajes

Yolanda Garc´ Ruiz (UCM) ıa

Teor´ de Aut´matas y Lenguajes Formales Tema 8. M´quinas d ıa o a

Introducci´n o Propiedades b´sicas de las MT a Definici´n formal de la MT o MT como aceptadoras de lenguajesBiograf´ ıa MT

Alan Mathison Turing Naci´ en Londres en el a˜o 1912 y muri´ en Cheshire en el o n o a˜o 1954 n Matem´tico, inform´tico te´rico, cript´grafo y fil´sofo ingl´s. a a o o o e Es considerado uno de los padres de la Ciencia de la computaci´n siendo el precursor de la inform´tica moderna. o a Proporcion´ una influyente formalizaci´n de los conceptos de o o algoritmo y computaci´n: lam´quina de Turing. o a

Yolanda Garc´ Ruiz (UCM) ıa

Teor´ de Aut´matas y Lenguajes Formales Tema 8. M´quinas d ıa o a

Introducci´n o Propiedades b´sicas de las MT a Definici´n formal de la MT o MT como aceptadoras de lenguajes

Biograf´ ıa MT

En 1937 public´ un c´lebre art´ o e ıculo en el que defini´ una o m´quina calculadora de capacidad infinita (m´quina de a a Turing) que operababas´ndose en una serie de instrucciones a l´gicas, sentando as´ las bases del concepto moderno de o ı algoritmo. As´ Turing describi´ en t´rminos matem´ticos precisos c´mo ı, o e a o un sistema autom´tico con reglas extremadamente simples a pod´ efectuar toda clase de operaciones matem´ticas ıa a expresadas en un lenguaje formal determinado. La m´quina de Turing era tanto un ejemplo de su teor´ de a ıacomputaci´n como una prueba de que un cierto tipo de o m´quina computadora pod´ ser construida. a ıa

Yolanda Garc´ Ruiz (UCM) ıa

Teor´ de Aut´matas y Lenguajes Formales Tema 8. M´quinas d ıa o a

Introducci´n o Propiedades b´sicas de las MT a Definici´n formal de la MT o MT como aceptadoras de lenguajes

Biograf´ ıa MT

Formul´ su propia versi´n de la hoy ampliamente aceptada o o Tesis deChurch-Turing, la cual postula que cualquier modelo computacional existente tiene las mismas capacidades algor´ ıtmicas, o un subconjunto, de las que tiene una m´quina a de Turing. La Segunda Guerra Mundial ofreci´ un insospechado marco de o aplicaci´n pr´ctica de sus teor´ al surgir la necesidad de o a ıas, descifrar los mensajes codificados que la Marina alemana empleaba para enviarinstrucciones a los submarinos que hostigaban los convoyes de ayuda material enviados desde Estados Unidos (los de la m´quina Enigma) a Turing, al mando de una divisi´n de la Inteligencia brit´nica, o a dise˜´ tanto los procesos como las m´quinas que, capaces de no a efectuar c´lculos combinatorios mucho m´s r´pido que a a a cualquier ser humano, fueron decisivos en la ruptura final del c´digo. o
YolandaGarc´ Ruiz (UCM) ıa

Teor´ de Aut´matas y Lenguajes Formales Tema 8. M´quinas d ıa o a

Introducci´n o Propiedades b´sicas de las MT a Definici´n formal de la MT o MT como aceptadoras de lenguajes

Biograf´ ıa MT

Defini´ adem´s un m´todo te´rico para decidir si una m´quina o a e o a era capaz de pensar como un hombre (test de Turing) La carrera de Turing termin´ s´bitamente cuando fue o u...