• Author / Uploaded
• KLMzr

Citation preview

INSTITUTO TECNOLÓGICO SUPERIOR DE LERDO INGENIERÍA EN SISTEMAS COMPUTACIONALES

MATERIA: ARQUITECTURA DE COMPUTADORAS.

ENSAYO: ORIGEN Y FUNCIONAMIENTO DE LA MAQUINA DE TOURING.

DOCENTE: ING. EDNA VELIA JOSEFINA SOLORIO VEGA

ALUMNOS: SALAZAR TALAVERA SAYROL FARIDE_12231145 VILLEGAS RIVERA LUIS MANUEL_12231387

GRUPO: V “A”

FECHA DE ENTREGA: LUNES 29 DE SEPTIEMBRE DE 2014

CD. LERDO DGO.

SEMESTRE: AGO-DIC 2014

Origen Alan Mathison Turing nació en 1912, y muy pronto mostró una extraordinaria intuición científica. Mientras su padre se hallaba en Madrás, trabajando para el Indian Civil Service, Turing ganó numerosos premios escolares, y más tarde una beca que le llevaría al King's College de Cambridge. Fue aquí cuando empezó a interesarse seriamente por los problemas de lógica matemática. En 1931, el matemático checo Kurt Godel descubrió que había teoremas matemáticos que eran verdaderos aun cuando no se pudiesen probar. Ante esto, Alan Turing se puso a investigar aquellos que sí podían ser probados. Quería intentar demostrar la vieja idea de que las matemáticas no son un arte misterioso, sino una ciencia exacta regida por reglas lógicas. Para hacerlo, ideó una máquina imaginaria capaz de realizar de manera totalmente mecánica los procesos que normalmente llevaría a cabo un matemático. Había una máquina para cada proceso; así, había una máquina que sumaba, otra que multiplicaba, etc. Estas máquinas acabarían por recibir el nombre de "Máquinas de Turing". Básicamente, lo que quería era hacer una lista de los problemas que una máquina sería capaz de resolver siguiendo reglas lógicas. Si esta lista abarcaba todos los problemas matemáticos, entonces su tesis quedaría demostrada, y con ella la teoría de la computabilidad. Tras estudiar con detenimiento el funcionamiento de sus máquinas, concluyó que era posible diseñar un artilugio único capaz de cumplir las funciones de cualquier otra máquina de Turing. A ésta se le llamó la "Máquina Universal de Turing". Al estallar la Segunda Guerra Mundial, Turing fue alejado del mundo académico y reclutado por la Escuela de Códigos y Cifrados del gobierno británico. Las actividades que realizaba consistían de manera primordial en descifrar el código militar alemán ENIGMA. Para ello desarrolló el invento más secreto de dicha guerra: el Colossus, primer ordenador electromecánico del mundo. Más adelante, sería destinado a los Estados Unidos con el fin de crear unos códigos seguros para las comunicaciones transatlánticas entre los países aliados.

Acabada la guerra, Turing colaboró en la construcción del ENIAC. Posteriormente recibió el encargo de empezar a trabajar en la construcción de un ordenador totalmente británico, destinado al National Physical Laboratory, y que recibiría el nombre de ACE (Automatic Computing Engine). Esta máquina tardó mucho tiempo en ser construida, pero era superior a ENIAC en muchas características. Frustrado por el lento avance, dimitió y se fue a vivir a Manchester, colaborando en el proyecto del MARK I, el ordenador de la universidad. Al mismo tiempo, era asesor de la compañía Ferranti y, por tanto, colaboró en la construcción de los primeros ordenadores fabricados en Gran Bretaña. En 1952, Turing fue acusado de homosexualidad, y dos años más tarde se suicidó. ¿Cómo funciona una máquina de Turing? Una máquina de Turing es un dispositivo que transforma un INPUT en un OUTPUT después de algunos pasos. Tanto el INPUT como el OUPUT constan de números en código binario (ceros y unos). En su versión original la máquina de Turing consiste en una cinta infinitamente larga con unos y ceros que pasa a través de una caja. La caja es tan fina que solo el trozo de cinta que ocupa un bit (0 o 1) está en su interior. La máquina tiene una serie de estados internos finitos que también se pueden numerar en binario. Para llevar a cabo algún algoritmo, la máquina se inicializa en algún estado interno arbitrario. A continuación, se pone 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). Después 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 por ejemplo. Una instrucción típica podría ser: 0111011i La traducción es como sigue: si la máquina se encuentra en el estado interno 0 y lee 1 en la cinta, entonces pasará al estado interno 1101 (13), escribirá 1 y se moverá hacia la izquierda un paso (la cinta se moverá hacia la derecha).

A continuación es conveniente inventar una notación para la secuencia del INPUT. Esta notación se llama notación binaria expandida. Consiste en cambiar la secuencia original binaria por otra construida de la siguiente forma: el 0 se cambia por 0 y el 1 por 10 y se ponen un cero a la izquierda y/o a la derecha del resultado si empieza o acaba en 1 respectivamente. Así por ejemplo, el número 13 que en binario es 1101 es en binario expandido 1010010 con un cero delante por esta última regla 01010010. Para volver al original hay que contraer el binario expandido con la siguiente regla: Empezamos a leer por la izquierda el binario expandido. Cuando encontremos un 0 tomamos nota de cuántos 1 hay hasta llegar al siguiente 0 y lo escribimos. Si encontramos que hay dos 0 seguidos, apuntaríamos un 0 porque no habría ningún 1.Veamos con el 13 cómo se haría. El primer 0 se encuentra en la primera posición y el siguiente 0 está en la posición 3. Entre los dos solo hay un 1. Lo anotamos. Seguidamente hay un 1, y después un 0, entonces apuntamos 1 porque hay un 1 entre medias de ellos. Esto es lo que se hace sucesivamente y encontramos: 1101 que es el número original. 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. El cómputo es determinado a partir de una tabla de estados de la forma: (Estado, valor) (Nuevo estado, nuevo valor, dirección)

Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a ser escrito en la cinta. La memoria será la cinta la cual se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo

especial

denominado

“blanco”.

Las

instrucciones

que

determinan

el

funcionamiento de la máquina tienen la forma, “si estamos en el estado x leyendo la posición y, donde hay escrito el símbolo z, entonces este símbolo debe ser reemplazado por este otro símbolo, y pasar a leer la celda siguiente, bien a la izquierda o bien a la derecha”. La máquina de Turing puede considerarse como un autómata capaz de reconocer lenguajes formales. En ese sentido es capaz de reconocer los lenguajes recursivamente innumerables, de acuerdo a la jerarquía de Chomsky. Su potencia es, por tanto, superior a otros tipos de autómatas, como el autómata finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional. Influencia en la computación Pero ha sido la contribución de Turing a descifrar el código Enigma Bletchley Park La que ha dado lugar a más obras literarias y cinematográficas. Destacamos la película “Breaking the code” rodada por Hugh Whitemore en 1996, y, sobre todo, la novela “Cryptonomicon” de Neal Stephenson, publicada en 1999, que en su versión castellana en Ediciones B fue dividida en tres volúmenes, el primero de los cuales llevaba por título precisamente “El código Enigma”. Alan Turing murió relativamente joven, un par de semanas antes de cumplir 42 años, tras ingerir una manzana envenenada con cianuro. Se supone que se suicidó, aunque no dejó ningún escrito que lo confirmara, presuntamente para que su madre pudiera seguir pensando que se trató de un descuido. Dos años antes, descubierta su homosexualidad accidentalmente por la policía, fue obligado a escoger entre la cárcel o la castración química, y optó por la segunda. Esto convirtió su vida en una pesadilla e hizo mucho daño a su reputación como científico dificultando su investigación. Se han escrito muchos libros sobre sus contribuciones a la teoría de la computación y también algunas biografías. Recomiendo “Alan Turing: The Enigma” de Andrew Hodges, Random House, segunda edición, 1992.

En definitiva, Alan Turing fue un científico singular que ha tenido una gran influencia en la historia de la informática y cuya prematura muerte probablemente nos privó de otras importantes contribuciones. Su trabajo constituye, sin duda, un eslabón destacado en la cadena de investigaciones conducentes a la aparición del computador digital. En mi opinión, se le ha escogido como estandarte para homenajear también a los muchos otros científicos que contribuyeron en mayor o menor medida a dicha cadena, desde Leibniz, con su sueño de un procedimiento universal de razonamiento, pasando por Babagge y Lovelace, los ya citados Hilbert y Gödel, y muy especialmente los colaboradores y coetáneos de Turing, como von Neumann, Newman, Eckert, Mauchly, Kleene, Church y Post, así como tantos otros investigadores sin cuyo concurso hoy el mundo no sería tan digital como es. A todos ellos, nuestro más sincero reconocimiento. Conclusiones Salazar Talavera Sayrol Faride En este ensayo concluimos que una Máquina de Turing, o MT, se considerar una cinta infinita dividida en casillas, cada una de las cuales contiene un símbolo, y sobre la cual actúa un dispositivo que puede adoptar diversos estados, y que lee un símbolo de la casilla sobre la que está situado. En función de dicho símbolo y del estado actual, se pueden realizar tres acciones siguientes: pasa a un nuevo estado, imprime un símbolo en lugar del que acaba de leer y se desplaza a una posición hacia la izquierda, derecha, o se detiene.

Conclusiones Villegas Rivera Luis Manuel Existen diversas clasificaciones de las Máquinas de Turing, atendiendo a los estados reconocidos, tipo de cinta, cantidad o división de dichas cintas: MT con directiva de permanecer, MT con cinta infinita en una dirección, MT en dos direcciones, MT multicinta, MT

Multidimensional,

MT

No

determinista.

Las MT, de acuerdo a la clasificación de los lenguajes formales de Chomsky, acepta los lenguajes tipo cero (0), llamados lenguajes recursivamente innumerables. La creación modular de una máquina de Turing permite desarrollar máquinas complejas a partir de bloq Bibliografía

Alfonseca, M; Sancho, J; Martínez Orga, M.A: Teoría de Lenguajes, Gramaticas y Autónomas. Promosoft, Publicaciones R.A.E.C…, Madrid, 1997, ISBN: 84-605-6092-9.