tfa lógica y computabilidad 2009/2010 sergio santander jiménez luis fernando pinero rodríguez
TRANSCRIPT
![Page 1: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/1.jpg)
Autómatas celularesEl juego de la vida
TFA Lógica y computabilidad2009/2010
Sergio Santander JiménezLuis Fernando Pinero Rodríguez
![Page 2: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/2.jpg)
Autómatas celulares◦ Historia◦ Patrones◦ Autómata de Von Neumann◦ Clasificación◦ Autómatas y computabilidad
El juego de la vida◦ Historia◦ Reglas◦ Patrones◦ Computación universal◦ Ejemplos
Índice
![Page 3: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/3.jpg)
Un autómata celular describe una idealización matemática de la naturaleza, proporcionando modelos para un amplio margen de complejos fenómenos biológicos y físicos.
Componentes:◦ Red o espacio celular.◦ Conjunto de reglas de transición.
Autómatas celularesIntroducción
![Page 4: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/4.jpg)
Red o espacio celular: un número N de celdas idénticas que pueden tomar valores finitos conectados entre sí. Los valores del próximo estado dependen de los valores actuales de los vecinos para una determinada celda.
Autómatas celularesIntroducción
![Page 5: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/5.jpg)
Conjunto de reglas de transición: Actualiza el valor de una determinada celda en función de los valores actuales de sus vecinos.
Ejemplo de ECAs (Elementary Cellular Automaton):
Autómatas celularesIntroducción
![Page 6: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/6.jpg)
1947 estudios de Von Neumann sobre modelos de robótica basados en ecuaciones diferenciales.
1952 primer autómata celular. Modelo abstracto de auto-reproducción biológica.
Década de los 60 conceptos de auto-reproducción y computación universal sobre autómatas de este tipo.
1968 el juego de la vida de John Conway. Abandonado en la década de los 70 y
retomada su investigación en 1983.
Autómatas celularesHistoria
![Page 7: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/7.jpg)
Ocurrencia de una serie de valores a lo largo del tiempo según una determinada configuración inicial o semilla.
Autómatas celularesPatrones
![Page 8: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/8.jpg)
Uso de autómatas celulares para obtener un sistema cuya organización lógica sea capaz de reproducirse por sí mismo.
Espacio celular de dos dimensiones infinito. 29 posibles estados por celda. Vecindad Von Neumann. Componentes:
◦ Unidad de construcción.◦ Unidad de cinta.
Autómatas celularesAutómata de Von Neumann
![Page 9: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/9.jpg)
Autómatas celularesAutómata de Von Neumann
![Page 10: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/10.jpg)
Una aproximación algebraica puede determinar la estructura de los patrones y de los valores obtenidos a través de las distintas transiciones de estados.
Ecuación general:
Autómatas celularesClasificación
![Page 11: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/11.jpg)
Variando esta ecuación se pueden obtener los siguientes autómatas:1. Cuya evolución da lugar a un estado
homogéneo, en el que todos los puntos tienen el mismo valor.
2. Cuya evolución conduce a un conjunto finito de estructuras (conjuntos de valores no siguiendo un patrón).
3. Cuya evolución sigue un determinado patrón. 4. Cuya evolución conlleva la aparición de
estructuras complejas que se mantienen en el tiempo.
Autómatas celularesClasificación
![Page 12: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/12.jpg)
Concepto de computador “universal”: aquel sistema en el que, dado un programa de entrada, sus pasos evolutivos pueden implementar cualquier algoritmo.
La entrada puede ser vista como un programa+datos y la secuencia final es el resultado de llevar a cabo los cálculos.
En autómatas celulares: diferentes configuraciones iniciales deben codificar todos los posibles programas mediante la definición de reglas evolutivas.
Autómatas celularesAutómatas y computabilidad
![Page 13: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/13.jpg)
La tesis de Church-Turing da a entender que ningún sistema tendrá una capacidad computacional mayor que estos computadores universales.
Computador universal en autómatas celulares mediante definición de estructuras que actúan como componentes básicos de los computadores digitales.
Autómatas celularesAutómatas y computabilidad
![Page 14: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/14.jpg)
Ejemplo: Un autómata de una dimensión con un rango de valores para cada uno de los puntos de la red con cardinalidad igual a dieciocho y con reglas basadas en los valores del vecino más próximo es equivalente a una máquina de Turing universal.
Ejemplo 2: Implementación de funciones lógicas en el juego de la vida.
Autómatas celularesAutómatas y computabilidad
![Page 15: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/15.jpg)
Ejemplo concreto de autómatas celulares:
El juego de la vida
![Page 16: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/16.jpg)
Concebido por matemático de origen británico John Horton Conway entre los años 1968 y 1970.
Juego de cero jugadores. Su evolución está determinada por su
estado o configuración inicial de la red.
El juego de la vidaIntroducción
![Page 17: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/17.jpg)
1968: evolución del concepto de autómata celular propuesto por Von Neumann.
1970: publicación en la revista “Scientific American”:
‘El juego hizo a Conway famoso al instante, pero también abrió todo un nuevo campo en la investigación matemática, el campo de los autómatas celulares… gracias a la analogía de la vida con el alzamiento, caída y alteraciones de la sociedad de los organismos vivientes’ – Martin Gardner.
El juego de la vidaHistoria
![Page 18: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/18.jpg)
Múltiples investigaciones que permitieron descubrir nuevos patrones en el juego. Computación universal.
Autómata celular más célebre: múltiples implementaciones y aplicaciones.
El juego de la vidaHistoria
![Page 19: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/19.jpg)
Toda celda viva con menos de dos vecinos vivos muere a causa de la baja población.
Cualquier celda viva con más de tres vecinos vivos muere a causa de superpoblación.
El juego de la vidaReglas
![Page 20: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/20.jpg)
Cualquier celda viva con dos o tres vecinos vivos en el estado actual vivirá en la siguiente generación.
Cualquier celda muerta con un total
exacto de tres vecinos vivos pasará a ser una celda viva.
El juego de la vidaReglas
![Page 21: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/21.jpg)
"Still lives"
El juego de la vidaPatrones
![Page 22: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/22.jpg)
El juego de la vida
1. Pulsar
2. Blinker
3. Beacon
4. Toad
Patrones - Osciladores
![Page 23: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/23.jpg)
“Methuselahs” (Matusalenes)
El juego de la vidaPatrones
![Page 24: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/24.jpg)
Spaceships o planeadores.◦ Glider
◦ LWSS
El juego de la vidaPatrones
![Page 25: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/25.jpg)
Patrones infinitos
◦ Glider Gun
◦ Otros
El juego de la vidaPatrones
![Page 26: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/26.jpg)
Demostrada por Berlekamp, Guy y Conway. Estructuras clave para la construcción de
computadores universales: “glider gun” y los propios “glider”.
Implementación de funciones lógicas: NOT, AND, OR, etc.
Simulación de máquina de Turing.
El juego de la vidaComputación universal
![Page 27: TFA Lógica y computabilidad 2009/2010 Sergio Santander Jiménez Luis Fernando Pinero Rodríguez](https://reader033.vdocumento.com/reader033/viewer/2022061303/54fc33ea4a7959e7528b4d69/html5/thumbnails/27.jpg)
FIN