Instituto Polit Ecnico Nacional
ESCOMIPNInstituto PolitécnicoNacionalEscuela Superior de CómputoTrabajo Terminal II – 2016-B044Máquinas de Turing y el problema dela universalidad como sistemasdinámicos discretosAutores:Juárez Martı́nez Sergio EduardoManzano Mendoza César IvánDirector:Dr. Genaro Juárez Martı́nezIng. en sistemas computacionales1 de noviembre de 2017Ing. en sistemas computacionalesITrabajo Terminal I
Índice generalÍndice de figurasIVÍndice de cuadrosVIResumenVII1. Introducción12. Estado del arte2.1. Autómatas celulares y reconocedores conectados en una dirección . . . . . . . .2.2. Autómatas móviles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3. Representación de las máquinas de Turing en dos dimensiones . . . . . . . . . .2.4. Autómatas celulares universales pequeños . . . . . . . . . . . . . . . . . . . . .2.4.1. El juego de la vida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.4.2. Capacidad de la regla 110 para simular una máquina de Turing . . . . .2.5. Autómatas celulares que simulan máquinas de Turing . . . . . . . . . . . . . . .2.5.1. La noción de computación . . . . . . . . . . . . . . . . . . . . . . . . . .2.5.2. Espacios celulares simples computacionalmente universales . . . . . . . .2.5.3. Simulación de autómatas celulares por autómatas celulares . . . . . . . .2.5.4. Computación universal en autómatas celulares unidimensionales simples .2.6. Máquinas de Turing universales . . . . . . . . . . . . . . . . . . . . . . . . . . .33456677778893. Marco teórico3.1. Teorı́a de autómatas y lenguajes formales3.1.1. Autómatas . . . . . . . . . . . . .3.1.2. Máquinas de Turing . . . . . . .3.1.3. Universalidad . . . . . . . . . . .3.2. Sistemas dinámicos discretos . . . . . . .3.3. Autómatas Celulares . . . . . . . . . . .3.3.1. Clases de autómatas celulares . .10101012141415174. Diseño4.1. Percepción de una dificultad . . . . . . . . . . . .4.2. Identificación y definición de la dificultad . . . . .4.3. Soluciones propuestas para el problema: hipótesis4.4. Verificación de la hipótesis mediante la acción . .2021212222II.
ESCOM5. Desarrollo del Software5.1. Máquinas de Turing . . . . . . . . .5.1.1. Opciones . . . . . . . . . . .5.1.2. Colours . . . . . . . . . . .5.1.3. Descripción de una máquinaIPN. . . . . . . . . . . . . . . .de Turing.23232627296. Modelo de un autómata celular computacionalmente universal6.1. Análisis de una máquina de Turing para el balanceo de paréntesis . . . . . . . .6.1.1. Descripción de la máquina . . . . . . . . . . . . . . . . . . . . . . . . . .6.1.2. Representación de la cinta de la máquina de Turing . . . . . . . . . . . .6.1.3. Construcción del autómata . . . . . . . . . . . . . . . . . . . . . . . . . .6.1.4. Representación de los movimientos a la derecha . . . . . . . . . . . . . .6.1.5. Representación de los movimientos a la izquierda . . . . . . . . . . . . .6.1.6. Descripción completa de la función de transición del autómata celular . .6.1.7. Condición de paro en el autómata . . . . . . . . . . . . . . . . . . . . . .6.2. Algoritmo para el cálculo de un autómata celular equivalente a una máquina deTuring arbitraria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.3. Aplicación del algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.3.1. Máquina para la suma binaria . . . . . . . . . . . . . . . . . . . . . . . .6.3.2. Máquina que simula la regla 110 . . . . . . . . . . . . . . . . . . . . . . .6.4. Reducción del número de sı́mbolos auxiliares . . . . . . . . . . . . . . . . . . . .6.5. Algoritmo para el cálculo de un autómata celular con pocos estados auxiliaresequivalente a una máquina de Turing arbitraria . . . . . . . . . . . . . . . . . .6.6. Autómata celular universal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.6.1. Elección de la máquina de Turing universal que se simulará . . . . . . . .6.6.2. Construcción del autómata celular . . . . . . . . . . . . . . . . . . . . . .3030303135353637417. Esbozo de una taxonomı́a inicial de las máquinas de Turing7.1. El conjunto de máquinas de Turing a analizar . . . . . . . . . . .7.1.1. La máquina 0n 1n . . . . . . . . . . . . . . . . . . . . . . .7.1.2. La máquina para el emparejamiento de paréntesis . . . . .7.1.3. La máquina duplicadora de unos . . . . . . . . . . . . . .7.1.4. La máquina sumadora . . . . . . . . . . . . . . . . . . . .7.1.5. La máquina para la resta unaria . . . . . . . . . . . . . . .7.1.6. La máquina de Turing universal con 7 estados y 4 sı́mbolos7.2. Esbozo de la taxonomı́a . . . . . . . . . . . . . . . . . . . . . . .5757585961626365668. ConclusionesIng. en sistemas computacionales.41424248515253535568IIITrabajo Terminal I
Índice de figuras2.1. Reconocedor conectado en una dirección que reconoce las cadenas de paréntesisbalanceados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2. Ejemplo de autómata móvil [6] . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3. Representación de una máquina de Turing en dos dimensiones[22] . . . . . . . .2.4. Descripción de la regla 110. [6] . . . . . . . . . . . . . . . . . . . . . . . . . . .3.1. Grafo para el autómata elemental correspondiente a la regla 90 con 16 celdas ensu espacio de evoluciones. Generado con Mathematica[12] . . . . . . . . . . . . .3.2. Grafo para el autómata elemental correspondiente a la regla 22 con 32 celdas ensu espacio de evoluciones. Generado con DDLab[13] . . . . . . . . . . . . . . . .3.3. Ejemplo del comportamiento del autómata elemental correspondiente a la regla32. Pertenece a la clase 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.4. Ejemplo del comportamiento del autómata elemental correspondiente a la regla4. Pertenece a la clase 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.5. Ejemplo del comportamiento del autómata elemental correspondiente a la regla30. Pertenece a la clase 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.6. Ejemplo del comportamiento del autómata elemental correspondiente a la regla110. Pertenece a la clase 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.1. Ventana inicial del programa . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.2. Gráfica de frecuencias de la máquina de Turing de emparejamiento de paréntesiscon la entrada ((())()) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.3. Menú Options. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.4. Menú Colours. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.5. Ventana de la opción Edit del menú Colours con la máquina de Turing de emparejamiento de paréntesis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.6. Menú para elegir color . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.1. Diagrama de transiciones de la máquina de Turing para el emparejamiento deparéntesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.2. Dinámica en dos dimensiones de la máquina para la cadena de entrada ((())()) .6.3. Dinámica en dos dimensiones de la máquina para el emparejamiento de paréntesiscon la cadena (((())))()((()))(()) . . . . . . . . . . . . . . . . . . . . . . . . . . .6.4. Dinámica en dos dimensiones del autómata para el emparejamiento de paréntesiscon la cadena a(((())))()((()))(()) . . . . . . . . . . . . . . . . . . . . . . . . . .6.5. Algoritmo para el cálculo de un autómata celular equivalente a una máquina deTuring arbitraria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .IV45671717181819192527272828293134394041
ESCOMIPN6.6. Dinámica en dos dimensiones de la máquina para el emparejamiento de paréntesiscon la cadena 011100 010000 . . . . . . . . . . . . . . . . . . . . . . . . .6.7. Dinámica en dos dimensiones del autómata para el emparejamiento de paréntesiscon la cadena a 011100 010000 . . . . . . . . . . . . . . . . . . . . . . . .6.8. Dinámica en dos dimensiones de la máquina que simula el funcionamiento de laregla 110 con la cadena 010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.9. Dinámica en dos dimensiones de la máquina que simula el funcionamiento de laregla 110 con la cadena a010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.10. Algoritmo para el cálculo de un autómata celular con pocos estados equivalentea una máquina de Turing arbitraria . . . . . . . . . . . . . . . . . . . . . . . . .7.1. Ejecución de la máquina 0n 1n con un tamaño inicial de 5000 carácteres y conposición inicial del cabezal aleatoria. Esta cinta inicial alcanzó las 63 generaciones.7.2. Ejecución de la máquina 0n 1n con un tamaño inicial de 10 carácteres y conposición inicial del cabezal a la izquierda de la cinta de entrada. Esta cintainicial alcanzó las 222 generaciones. . . . . . . . . . . . . . . . . . . . . . . . . .7.3. Ejecución de la máquina para el emparejamiento de paréntesis con un tamañoinicial de 300 carácteres y con posición inicial del cabezal aleatoria. Esta cintainicial alcanzó las 938 generaciones. . . . . . . . . . . . . . . . . . . . . . . . . .7.4. Ejecución de la máquina para el emparejamiento de paréntesis con una cadenainicial de 20 carácteres y con posición inicial del cabezal en el extremo izquierdode la cinta de entrada. Esta cinta inicial alcanzó las 463 generaciones (más queen promedio de forma aleatoria) . . . . . . . . . . . . . . . . . . . . . . . . . . .7.5. Ejecución de la máquina duplicadora de unos con una cadena inicial de 20carácteres y con posición inicial del cabezal en el extremo izquierdo de la cintade entrada. Esta cinta inicial alcanzó las 233 generaciones (más de el triple queel máximo obtenido en el experimento) . . . . . . . . . . . . . . . . . . . . . . .7.6. Ejecución de la máquina sumadora con una cadena inicial de 1000 carácteresaleatorios y con posición inicial del cabezal aleatoria. Esta cinta inicial alcanzólas 1001 generaciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7.7. Ejecución de la máquina para la resta unaria con una cadena inicial de 1000carácteres aleatorios y con posición inicial del cabezal aleatoria. Esta cinta inicialalcanzó las 825 generaciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7.8. Ejecución de la máquina para la resta unaria con una cadena inicial 31 carácteresarbitrarios el cabezal a la izquierda de la cadena de entrada. Esta cinta inicialalcanzó las 513 generaciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7.9. Ejecución de la máquina de Turing universal con 7 estados y 4 sı́mbolos con unacadena inicial 1000 carácteres con el cabezal en una posición inicial aleatoriasobre la cadena de entrada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Ing. en sistemas o Terminal I
Índice de cuadros6.1. Función de transición para la máquina de Turing para el emparejamiento deparéntesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.2. Lista de descripciones instantáneas al analizar la cadena ((())()) . . . . . . . . .6.3. Transiciones del autómata celular que simulan el movimiento de la máquina deTuring a la derecha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.4. Transiciones del autómata celular que simulan la transición δha, (i ha, (, Ri dela máquina de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.5. Evolución del autómata celular para los movimientos a la derecha . . . . . . . .6.6. Transiciones del autómata celular para simular la transición δha, )i hb, X, Lide la máquina de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.7. Evolución del autómata celular con movimientos a la izquierda . . . . . . . . . .6.8. Descripción de la función de transición del autómata celular equivalente . . . . .6.9. Evolución del autómata para la cadena ((())()) . . . . . . . . . . . . . . . . . . .6.10. Función de transición para la máquina de Turing que realiza una suma binaria .6.12. Descripción de la función de transición del autómata celular equivalente a lamáquina que realiza una suma binaria . . . . . . . . . . . . . . . . . . . . . . .6.13. Función de transición para la máquina de Turing que simula la regla 110 . . . .6.14. Descripción de la función de transición del autómata celular equivalente a lamáquina que simula la regla 110 . . . . . . . . . . . . . . . . . . . . . . . . . . .6.15. Ejemplo de sı́mbolos auxiliares con un comportamiento casi idéntico . . . . . . .6.16. Ejemplo de reglas ambiguas . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.17. Reglas para simular una transición de la forma δ(p, X) (q, Y, L) . . . . . . . .6.18. Regla para desplazar el cabezal a la izquierda . . . . . . . . . . . . . . . . . . .6.19. Evolución del autómata celular para los movimientos a la derecha . . . . . . . .6.20. Máquinas de Yurii Rogozhin . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.21. Función de transición para la máquina U T M (7, 4) . . . . . . . . . . . . . . . . .6.22. Función de transición para la máquina U T M (5, 5) . . . . . . . . . . . . . . . . .6.23. Función de transición para la máquina U T M (4, 6) . . . . . . . . . . . . . . . . .6.24. Estados necesarios para simular cada máquina . . . . . . . . . . . . . . . . . . .6.26. Descripción de la función de transición del autómata celular equivalente a lamáquina que simula la regla 110 . . . . . . . . . . . . . . . . . . . . . . . . . . 6
ResumenEn el presente documento se desarrolla la primera parte de una investigación que comprendeel análisis de las máquinas de Turing y el fenómeno de la universalidad como sistemas dinámicos discretos. Con este propósito, buscamos crear una relación entre las máquinas de Turingy los autómatas celulares, de manera tal que estos últimos (los autómatas celulares) puedancomportarse como las máquinas de Turing. El trabajo terminal tiene como fines últimos la construcción de un autómata celular computacionalmente universal y el esbozo de una taxonomı́aque clasifique a las máquinas de Turing.Los resultados que aquı́ se presentan incluyen el marco teórico, que contiene la definiciónformal de los conceptos necesarios para el desarrollo del trabajo; el estado del arte, en donde seexponen varios trabajos que se relacionan con nuestro proyecto o bien, que contienen resultadosy observaciones que proporcionan un enfoque distinto al que nosotros hemos desarrollado paratratar conceptos semejantes; la descripción de la metodologı́a que se utilizará, en donde seespecifican las actividades que realizaremos a lo largo de esta investigación y finalmente losavances, en donde se muestra la documentación de las herramientas que hemos desarrollado yel análisis de una máquina de Turing clásica que nos ha llevado a la formulación de un algoritmocapaz de calcular un autómata celular equivalente a una máquina de Turing arbitraria.VII
Capı́tulo 1IntroducciónEn 1936, Alan Mathison Turing desarrolló la conocida máquina de Turing como modelo parareconocer cualquier lenguaje formal a través de un procedimiento efectivo. Básicamente, estedispositivo es una máquina de estados finitos que dispone de una cinta de longitud infinita en laque se pueden leer y escribir datos. La máquina de Turing es lo suficientemente simple como paraque podamos representar su configuración de manera precisa, utilizando una notación sencilla.La capacidad de estas máquinas para el reconocimiento de lenguajes formales les concede elmismo potencial para la resolución de problemas que una computadora actual, pues podemosplantear todos los problemas computables como una cuestión acerca de si un problema perteneceo no a un lenguaje determinado.La teorı́a de los sistemas dinámicos describe en términos generales la forma en la que puedencambiar los sistemas, qué tipos de comportamientos macroscópicos son posibles y qué tipo depredicciones sobre su evolución pueden realizarse, proporcionando un conjunto de herramientaspara su estudio y análisis. Los sistemas dinámicos comprenden casi cualquier tipo de sistemaimaginable, y pueden desarrollarse en tiempo y espacio continuos y discretos. Un muy claroejemplo de este tipo de sistemas en tiempo y espacio discretos son los autómatas celulares.Desde su creación hace más de 80 años, las máquinas de Turing han sido estudiadas a travésde sus descripciones instantáneas (es decir, la configuración global de la máquina en un pasode tiempo especı́fico durante el proceso en el que resuelve si una cadena pertenece o no a unlenguaje determinado). Es por ello que, en el presente Trabajo Terminal, se propone utilizarun nuevo enfoque para su estudio, concibiéndolas como sistemas dinámicos discretos.El presente documento comprende el desarrollo y los resultados de una investigación cuyopunto de partida es la consideración de las máquinas de Turing como sistemas dinámicos discretos y cuyos objetivos se concentran en las hipótesis planteadas; Existe un algoritmo tal que,tomando como entrada la descripción formal de una máquina de Turing arbitraria, devuelvecomo resultado un autómata celular capaz de simular a dicha máquina y Puede obtenerse unautómata celular universal a través de la aplicación del algoritmo anteriormente mencionado auna máquina de Turing universal.En primer lugar se abordó la problemática de la representación de las máquinas de Turingque, como fué mencionado con anterioridad, han sido estudiadas a través de sus descripcionesinstantáneas. Para ello se desarrolló una aplicación de escritorio capaz de desplegar la dinámicaen dos dimensiones de cualquier máquina de Turing que lee una cadena de entrada. Dicha aplicación cuenta también con un conjunto de herramientas para el análisis de su comportamiento.A continuación se analizó una máquina de Turing en particular, logrando obtener de ella1
ESCOMIPNun autómata celular equivalente. Dicho autómata celular fue útil a su vez para desarrollar unalgoritmo general, tal que, tomando como entrada la descripción formal de una máquina deTuring, produjera como salida la especificación de las reglas de un autómata celular equivalentea dicha máquina, comprobando la primera hipótesis.El algoritmo general fue modificado para producir autómatas celulares más pequeños y posteriormente utilizado para obtener un autómata celular computacionalmente universal (comprobando ası́ la segunda hipótesis). Para ello fueron consideradas las máquinas de Turing universales determinı́sticas de una cinta más pequeñas que se han encontrado. El análisis de dichasmáquinas se incluye como parte de la investigación.Ing. en sistemas computacionales2Trabajo Terminal I
Capı́tulo 2Estado del arte2.1.Autómatas celulares y reconocedores conectados enuna direcciónLos reconocedores conectados en una dirección son un modelo que utiliza los autómatascelulares para el reconocimiento de lenguajes. Un autómata celular conectado en una direcciónes un autómata celular de una dimensión en el que el único vecino de una célula es la célulainmediatamete a su izquierda. Formalmente, una célula o celda conectada en una direcci
Instituto Polit ecnico Nacional Escuela Superior de Computo Trabajo Terminal II { 2016-B044 . Introducci on1 2. Estado del arte3 . Ejecuci on de la m aquina 0 n1 con un tamano inicial de 5000 car acteres y con posici on inicial del cabezal aleatoria. Esta cinta inicial alcanz o las 63 generaciones.58
Hermenegildo Galena 3, 56615 Valle de Chalco, M exico 4 Centro de Innovaci on y Desarrollo Tecnol ogico en C omputo, Instituto Polit ecnico Nacional, Av. Juan de Dios B atiz s/n, Col. Nueva Industrial Vallejo, 07700 M exico D.F., M exico Abstract. Hybrid associative memories are based on the combination of two
Francisco J. Múgica (FJM) Instituto de Investigaciones Sociales y Económicas (IIES) Instituto Nacional de Antropología e Historia (INAH) Instituto Nacional de Educación Superior para Trabajadores (INEST) Instituto Nacional de Estudios Históricos de la Revolución Mexicana (INEHRM) 6.
Haciendo hologramas en la escuela y en la casa (Making holograms at school and at home) Rolando Serra Toledo1, Alfredo Moreno Yeras1, Daniel S.F. Magalh aes2, Mikiya Muramatsu3 y Jos¶e B. Lemus4 1Departamento de F¶‡sica, Instituto Superior Polit¶ecnico Jos¶e Antonio Echeverr¶‡a, Ciudad de la Habana, Cuba
INE Instituto Nacional Electoral INEGI Instituto Nacional de Estadística y Geografía . Tanto los Consensos Regionales como la Estrategia de Monte- video (2016) han definido de manera muy clara que la ruta hacia la igualdad entre mujeres y hombres tiene una enorme relevancia
2. comisiÓn de administraciÓn de divisas – cadivi 3. instituto nacional de capacitaciÓn y educaciÓn socialista - inces 4. instituto nacional de desarrollo de la pequeÑa y mediana industria - inapymi 5. instituto nacional de prevenciÓn, salud y seguridad laborales – inpsasel 6.
Marlens Fernanda Carabalí Vernaza, Andrés Eduardo Enciso Moreno, Andrés Hernández Castellanos, Eduardo Antonio Ospina Álvarez, Tania Caterine Ramírez Lozano, Fredy Alejandro Rodríguez Salazar. MINISTERIO DE EDUCACIÓN NACIONAL Instituto Nacional para Ciegos - INCI Claudia Alejandra Valdés Laguna Instituto Nacional para Sordos - INSOR
tomado forma legal en el plano nacional.Por su parte, la Administración de Parques Nacionales se rige desde 1970 ( Ley Nacional Nº 18.594) por un régimen propio con tres categorías de manejo: Parque Nacional, Monumento Natural Nacional y Reserva Nacional, las que son equiparables con las categorías II, III y VI de la UICN respectivamente.
piece of paper and draw an outline of your chosen animal or person. 2. sing and dance when they If you would like to make more than one of any animal or person, fold your paper a few times behind the outline. You could also cut out your outline and trace around it. 3. from things they may Think of how to connect your paper animals or people.
