1 AUTÓMATAS CELULARES Andrés Pérez López Marzo 2012 Development of a SuperCollider3 Class Library for Algorithmic Composition by Means of Cellular Automata’s Sonification

2 AUTÓMATAS CELULARES Estructura de la presentación: Autómatas Celulares Composición Algorítmica SuperCollider Implementación

3 AUTÓMATAS CELULARES Estructura: Desarrollo histórico Autómatas Celulares Elementales Comportamiento y Clasificación Ampliación del concepto Aplicaciones

4 AUTÓMATAS CELULARES DESARROLLO HISTÓRICO 1940 – 1970 John von Neumann: Self-replication machines Wikimedia

5 AUTÓMATAS CELULARES DESARROLLO HISTÓRICO 1970 – 1983 J. H. Conway: Game of Life (23/3) Imágenes de Wikimedia Block Blinke r Glider

6 AUTÓMATAS CELULARES DESARROLLO HISTÓRICO 1970 – 1983 J. H. Conway: Game of Life (23/3) Kieff,Wikimedia

7 AUTÓMATAS CELULARES DESARROLLO HISTÓRICO 1983 S. Wolfram: Statistical mechanics of cellular automata Estudio sistemático autómatas simples Desarrollo notación estándar Clasificación comportamiento E.W.Weisstein, MathWorld

8 AUTÓMATAS CELULARES DESARROLLO HISTÓRICO Statistical mechanics of cellular automata Definición: autómata celular Modelo sistema físico con espacio y tiempo discreto Rejilla 1-dimensional uniforme y periódica Cada elemento (célula) posee en cada instante un estado de entre un número k de posibles estados El estado de una célula depende de su estado y el de sus adyacentes (en un radio r) en el instante anterior Todas las células se actualizan síncronamente mediante la misma transformación o regla local

9 AUTÓMATAS CELULARES AUTÓMATAS ELEMENTALES Autómatas más simples k=2 (2 estados) r=1 (2 vecinos) k k m = 256 reglas diferentes (m=2r+1) E.W.Weisstein, MathWorld

10 AUTÓMATAS CELULARES AUTÓMATAS ELEMENTALES Autómatas más simples ¿simples? E.W.Weisstein, MathWorld

11 AUTÓMATAS CELULARES COMPORTAMIENTO Y CLASIFICACIÓN Múltiples enfoques y propuestas: Análisis Cualitativos Wolfram 1984 Li & Packard 1990 Análisis Cuantitativos Wuensche 1998: Input Entropy Parametrización Langton 1990: λ

12 AUTÓMATAS CELULARES COMPORTAMIENTO Y CLASIFICACIÓN Clasificación de Wolfram (1984) Examen exhaustivo de patrones espacio-temporales 4 clases de comportamiento: Clase I: estado final homogéneo Clase II: estado final periódico Clase III: evolución caótica Clase IV: estructuras complejas

13 AUTÓMATAS CELULARES COMPORTAMIENTO Y CLASIFICACIÓN Parametrización: λ (Langton 1990) Caracterización a partir de la expresión de la tabla de reglas Parametriza el orden M.Frame, Yale University

14 AUTÓMATAS CELULARES COMPORTAMIENTO Y CLASIFICACIÓN Clasificación de Wolfram (1984) Clase I E.W.Weisstein, MathWorld

15 AUTÓMATAS CELULARES COMPORTAMIENTO Y CLASIFICACIÓN Clasificación de Wolfram (1984) Clase II E.W.Weisstein, MathWorld

16 AUTÓMATAS CELULARES COMPORTAMIENTO Y CLASIFICACIÓN Clasificación de Wolfram (1984) Clase III (regla 30) E.W.Weisstein, MathWorld

17 AUTÓMATAS CELULARES COMPORTAMIENTO Y CLASIFICACIÓN Clasificación de Wolfram (1984) Clase IV (regla 110) Maksim, Wikimedia

18 AUTÓMATAS CELULARES COMPORTAMIENTO Y CLASIFICACIÓN Clasificación de Wolfram (1984) Clase IV Aparecen estructuras localizadas que interactuan de forma complicada Sistema Turing completo más simple Ejemplo de sistema emergente

19 AUTÓMATAS CELULARES COMPORTAMIENTO Y CLASIFICACIÓN Comportamiento complejo o emergente: El comportamiento macro/colectivo del sistema no puede explicarse a partir del comportamiento de los elementos micro/individuales por separado Resolución de problemas de forma ascendente Autoorganización, estructura no jerárquica

20 AUTÓMATAS CELULARES COMPORTAMIENTO Y CLASIFICACIÓN Comportamiento complejo o emergente Wikimedia

21 AUTÓMATAS CELULARES COMPORTAMIENTO Y CLASIFICACIÓN Comportamiento complejo o emergente Sistemas físicos: Crecimiento cristales, temperatura Sistemas biológicos: Seres vivos, células, colonias de hormigas Sistemas sociales: Urbanismo, tráfico, mercados Psicología: gestalt Implicaciones filosóficas

22 AUTÓMATAS CELULARES AMPLIACIÓN DEL CONCEPTO Varios estados: k > 2 Ampliación vecindad: r > 1 Número de reglas: k k m (m=2r+1) Espacio de reglas k2r2: 4294967296 reglas W.Li, Complex Patterns Generated by Next Nearest Neighbors Cellular Automata : “Even if we can produce a spatial-temporal pattern from each rule in 1 second, it is going to take about 138 years to run through all the rules...”

23 AUTÓMATAS CELULARES AMPLIACIÓN DEL CONCEPTO Reglas Totalísticas La evolución depende del número de células activas en la vecindad y no de su posición Subconjunto de reglas representativo Andrés Pérez López

24 AUTÓMATAS CELULARES AMPLIACIÓN DEL CONCEPTO Autómatas celulares contínuos Las células tienen un rango contínuo de estados Espacio y tiempo discretos Transición: combinación lineal valores vecindad 1D continuous cellular automata

25 AUTÓMATAS CELULARES AMPLIACIÓN DEL CONCEPTO Autómatas 2-dimensionales Andrés Pérez López

26 AUTÓMATAS CELULARES AMPLIACIÓN DEL CONCEPTO Autómatas 2-dimensionales Posibles vecindades: Posibles particiones del plano: Grontesca, Wikimedia Andrés Pérez López

27 AUTÓMATAS CELULARES AMPLIACIÓN DEL CONCEPTO Autómatas 2-dimensionales Caso más simple (vecindad de 4): 65536 reglas Ausencia de notación, estructura Familias de reglas: Cellular automata rules lexiconCellular automata rules lexicon

28 AUTÓMATAS CELULARES AMPLIACIÓN DEL CONCEPTO Autómatas 3-dimensionales Akkramm, Wikimedia

29 AUTÓMATAS CELULARES AMPLIACIÓN DEL CONCEPTO Infinidad de modificaciones: Autómatas asíncronos Autómatas probabilísticos Autómatas de orden N Redes Booleanas … ¿Límite del concepto de autómata celular?

30 AUTÓMATAS CELULARES APLICACIONES Simulaciones y modelos Matemáticas Física Química Biología Sociología Economía Implicaciones filosóficas y metafísicas Digital Philosophy Richard Ling, Wikimedia

31 AUTÓMATAS CELULARES CONCLUSIÓN Modelo matemático de la realidad Muy simple computacionalmente Gran variedad de comportamientos estable, periódico, complejo, caótico Parametrización: “preveer” el comportamiento

32 AUTÓMATAS CELULARES RECURSOS Académicos Wolfram, S: A new Kind of ScienceA new Kind of Science Cerdà, J. y Gadea, R: Introducció als sistemes complexos, als autòmats cel·lulars i a les xarxes neuronals. UPV Ref 2009 – 3581 Software Mirek’s Java Cellebration Matlab, Mathematica

33 AUTÓMATAS CELULARES www.andresperezlopez.com [email protected]