Presentación del grupo 7043 - 2011-2.

Complejidad y autoorganización en modelos computacionales

Resumen

En la actualidad ha surgido un gran interés por el estudio de los modelos de cómputo cuya evolución esta dada por interacciones locales entre sus componentes debido a la gran complejidad que pueden generar y la sencillez con la que pueden ser definidos, entre estos se encuentran los autómatas celulares, los modelos multiagentes y las máquinas de Turing; la relación que existe entre todos estos sistemas es la noción de computabilidad y autoorganización.

La autoorganización es un proceso subyacente a la definición del sistema caracterizado por su dinámica espacial y temporal, a menudo exhiben propiedades emergentes como formación de patrones y capacidades de cómputo.

Estas propiedades de los sistemas han resultado de gran utilidad para entender y explicar procesos físicos, químicos, biológicos, sociales y computacionales, por ejemplo el comportamiento colectivo de organismos (aves, hormigas, termitas), formación de patrones en reacciones químicas oscilantes, incendios forestales, dinámicas de epidemias, las propiedades de cómputo universal en el “juego de la vida”, patrones en máquinas de Turing bidimensionales.

Durante el curso se analizarán los ejemplos antes mencionados a través de simulaciones computacionales, se estudiarán sus propiedades dinámicas, tales como puntos de equilibrio, periodicidad, caos y la capacidad de transmitir información.

Temario

1.Introducción a los modelos computacionales simples

2.Autómatas celulares

1.Definición

2.Dinámica del autómata celular elemental (ACE)

3.Análisis de las 256 Reglas

4.Dinámica de autómatas celulares totalísticos

2.Autómata móvil

1.Definición y exploración de dinámicas

2.Ejemplos.

3.Máquinas de Turing

1.Definición

2.Dinámica

3.Ejemplos

4.Sistemas de sustitución

1.Definición, dinámica, ejemplos

2.Sistemas de sustitución secuenciales

3.L-Systems

5.Sistemas de etiquetado

1.Definición, dinámica

2.Sistemas de etiquetado cíclicas

3.Máquinas de registro

6.Sistemas simbólicos

7.Sistemas basados sobre números

8.Sistemas de funciones iteradas (IFS)

1.Juego del Caos

2.Aplicaciones

9.Dinámica de sistemas computacionales

1.Puntos de equilibrio y periodicidad

2.Inestabilidad y caos

3.Transiciones de fase

4.Irreductibilidad

5.Irreversibilidad

10.Emergencia

1.Emergencia de patrones en 1D

2.Emergencia de patrones en 2D

1.Ejemplos

3.Emergencia de cómputo

4.Sistemas complejos

1.Sistemas complejos adaptables

2.Ejemplos

11.Computo y Universalidad

1.Cómputo en autómatas celulares

2.Fenómeno de la universalidad

3.Autómata celular universal

4.Emulación de sistemas

5.Universalidad en máquinas de Turing

Bibliografía

·Wolfram, Stephen, "A new kind of science", Wolfram Media, 2002.

·Ilachinski, Andrew, "Cellular Automata. A discrete universe", World Scientific, USA, 2001.

·Goles, Eric, et. al., "Cellular Automata and Complex Systems", Kluwer Academic Publishers, USA, 1999.

·Solé, Ricard, et. al., "Orden y caos en sistemas complejos", Edicions UPC, Barcelona, 1996.

·William F, Gary, "The Computational Beauty of Nature", The MIT Press, 1998.