Cellular Automata PDF

Cellular Automata Luı́s Correia CA Cellular Automata Luı́s Correia [email protected] http://di.ciencias.ulisboa.pt/~lcorreia Universidade de Lisboa, FC/DI - Portugal...

Cellular Automata Luı́s Correia CA Cellular Automata Luı́s Correia [email protected] http://di.ciencias.ulisboa.pt/~lcorreia Universidade de Lisboa, FC/DI - Portugal Vida Artificial / Modelos de Computação  Cellular Automata Luı́s Correia CA 1 Cellular Automata In two words von Neumann’s model In two words Properties of CA Wolfram classification von Neumann’s model Life Properties of CA Wolfram classification Life  The concept of CA Cellular Automata Luı́s Correia CA In two words von Neumann’s model Properties of CA Proposed ∼1950 by von Neumann and Ulam Wolfram classification to model biological reproduction Life Definition Infinite set of finite automata, with spacial organisation  Terminology Cellular Automata Luı́s Correia Finite automaton CA State machine ⇒ transition function In two words von Neumann’s model Spatial organisation Properties of CA Space division in identical elements with geometry Wolfram classification ⇒ a NEIGHBOURHOOD Life the spatial element and its finite automaton = one cell Input States of neighbour automata Output Automaton state Temporal evolution of CA Successive states of all cells  Properties and Applications Cellular Automata Luı́s Correia CA In two words CA are capable of universal computation ⇔ universal Turing von Neumann’s model machine Properties of CA Wolfram classification Interesting for Life Modeling spatial collective phenomena Fluid dynamics Diffusion and equilibrium forest fires for direct visual observation  a theory of reproduction idea Cellular Automata Luı́s Correia CA In two words The idea: von Neumann’s model Properties of CA Wolfram If X is an automaton classification Life and Φ(X) its description an automaton A is needed to interpret the description an to build a new X but...  a theory of reproduction idea Cellular Automata Luı́s Correia CA In two words The idea: von Neumann’s model Properties of CA Wolfram If X is an automaton classification Life and Φ(X) its description an automaton A is needed to interpret the description an to build a new X but...  a theory of reproduction paradox Cellular Automata Luı́s Correia CA In two words von Neumann’s to assure system’s autonomy it would be needed model Properties of CA Wolfram classification to have also Φ(A) Life and that A could interpret its own description Paradox! and we still need an entity to make copies of descriptions  a theory of reproduction paradox Cellular Automata Luı́s Correia CA In two words von Neumann’s to assure system’s autonomy it would be needed model Properties of CA Wolfram classification to have also Φ(A) Life and that A could interpret its own description Paradox! and we still need an entity to make copies of descriptions  a theory of reproduction paradox Cellular Automata Luı́s Correia CA In two words von Neumann’s to assure system’s autonomy it would be needed model Properties of CA Wolfram classification to have also Φ(A) Life and that A could interpret its own description Paradox! and we still need an entity to make copies of descriptions  a theory of reproduction complete system Cellular Automata Luı́s Correia the complete self-reproductive system CA In two words (A, B, C) + Φ(A, B, C) von Neumann’s model Properties of CA Wolfram classification description: Life three automata (A, B, C) A - creates automata from their descriptions B - copies descriptions C - maintains descriptions and supplies them to B and A and a joint description Φ(A, B, C)  a theory of reproduction modus operandi Cellular Automata Luı́s Correia CA In two words how it works von Neumann’s model Properties of CA 1 C supplies the description to B Wolfram classification Life 2 B copies the description 3 times (destroying the original) 3 C supplies one of the copies to A, which creates a new automaton (consuming the description) 4 C supplies another copy to the new automaton and keeps the third one (for further reproductions)  a theory of reproduction modus operandi illustrated Cellular Automata Luı́s Correia CA In two words von Neumann’s model Properties of CA Wolfram classification Life  Reproduction system evolving Cellular Automata Integrating evolution Luı́s Correia CA Suppose a new automaton D, in the system, which does not In two words affect normal reproduction process, i.e. of (A, B, C) von Neumann’s model Properties of CA Wolfram If there is a mutation in part D of the description (D → D′ ), classification Life then we’ll have a system (A, B, C, D) + Φ(A, B, C, D′ ) which will have as offspring the system (A, B, C, D′ ) + Φ(A, B, C, D′ ) Only mutations on the description affect offspring  Reproduction system evolving Cellular Automata Integrating evolution Luı́s Correia CA Suppose a new automaton D, in the system, which does not In two words affect normal reproduction process, i.e. of (A, B, C) von Neumann’s model Properties of CA Wolfram If there is a mutation in part D of the description (D → D′ ), classification Life then we’ll have a system (A, B, C, D) + Φ(A, B, C, D′ ) which will have as offspring the system (A, B, C, D′ ) + Φ(A, B, C, D′ ) Only mutations on the description affect offspring  self-reproducing system Cellular Automata Luı́s Correia CA In two words von Neumann’s von Neumann model Properties of CA 29 states, ∼ 105 cells Wolfram classification Codd Life 8 states, ∼ 3 × 108 cells Langton 8 states, 86 cells (but not universal...)  Main parameters Cellular Automata Luı́s Correia Dimension - d CA In two words 1D, 2D, 3D von Neumann’s model Properties of CA Wolfram Geometry classification Life quadrangular, hexagonal, triangular Number of states in each automaton - k Updating procedure Synchronous Asynchronous - sequential (fixed or random) or timed  Neighbourhood geometry and radius Cellular von Neumann Moore Automata Luı́s Correia CA In two words von Neumann’s model Properties of CA Wolfram classification Life Margolus Neighbourhood radius - r  Important features Cellular Automata Luı́s Correia Locality CA In two words Neighbourhood is finite ⇒ no instantaneous propagation von Neumann’s model at distance - Excludes synchronous updating Properties of CA Wolfram classification Reversibility Life Each configuration has a unique configuration that lead to it ⇒ the CA may run backwards in time Uniformity All cells have the same automaton Commonly: Locality and Uniformity  1 d CA Cellular Automata Luı́s Correia CA simplest case In two words von Neumann’s two states: k = 2 model neighbourhood radius one: r = 1 Properties of CA Wolfram the binary state of each cell depends on its own state and classification Life on the states of their two neighbours: 3 bits neighbourhood value 000 0 001 1 010 2 transition function 011 3 100 4 101 5 110 6 111 7  1 d CA rules Cellular Automata Luı́s Correia CA In two words von Neumann’s model Properties of CA Wolfram classification Life 28 = 256 possible transition functions a function is represented by 8 bits (rule) each bit designates the next state of the corresponding neighbourhood neighbourhood is the binary configuration corresponding to the position (0-7) of each bit in the byte  example rule Cellular Automata Luı́s Correia rule 30 CA In two words von Neumann’s model Properties of CA Wolfram classification Life rule = 21 + 22 + 23 + 24 = 2 + 4 + 8 + 16 = 30 source https://mathworld.wolfram.com/ElementaryCellularAutomaton.html  other example rule Cellular Automata Luı́s Correia CA In two words von Neumann’s model rule 22 Properties of CA Wolfram classification 22 in binary: 00010110 Life next state is 1 for neighbourhood of configurations {001, 010, 100} in all other configurations the next sate is 0  Wolfram classification Cellular Automata Luı́s Correia CA In two words von Neumann’s model Properties of CA Empiric classification Wolfram classification by visual observation Life Evaluates CA dynamics, in time and space(!) CA without external input some initial state is defined an the CA is run  Classes by Wolfram Cellular Automata Homogeneous or Fixed Point - Class I Luı́s Correia quickly converges to CA In two words homogeneous state von Neumann’s model Heterogeneous or Periodic - Class II Properties of CA Wolfram classification quickly converges to a Life constant structure or periodic Chaotic - Class III Irregular and long term unpredictable Complex - Class IV Irregular repetition with complex interactions  Classes by Wolfram Cellular Automata Homogeneous or Fixed Point - Class I Luı́s Correia quickly converges to CA In two words homogeneous state von Neumann’s model Heterogeneous or Periodic - Class II Properties of CA Wolfram classification quickly converges to a Life constant structure or periodic Chaotic - Class III Irregular and long term unpredictable Complex - Class IV Irregular repetition with complex interactions  Classes by Wolfram Cellular Automata Homogeneous or Fixed Point - Class I Luı́s Correia quickly converges to CA In two words homogeneous state von Neumann’s model Heterogeneous or Periodic - Class II Properties of CA Wolfram classification quickly converges to a Life constant structure or periodic Chaotic - Class III Irregular and long term unpredictable Complex - Class IV Irregular repetition with complex interactions  Classes by Wolfram Cellular Automata Homogeneous or Fixed Point - Class I Luı́s Correia quickly converges to CA In two words homogeneous state von Neumann’s model Heterogeneous or Periodic - Class II Properties of CA Wolfram classification quickly converges to a Life constant structure or periodic Chaotic - Class III Irregular and long term unpredictable Complex - Class IV Irregular repetition with complex interactions  Classes by Wolfram Cellular Automata Homogeneous or Fixed Point - Class I Luı́s Correia quickly converges to CA In two words homogeneous state von Neumann’s model Heterogeneous or Periodic - Class II Properties of CA Wolfram classification quickly converges to a Life constant structure or periodic Chaotic - Class III Irregular and long term unpredictable Complex - Class IV Irregular repetition with complex interactions  Classes by Wolfram Cellular Automata Homogeneous or Fixed Point - Class I Luı́s Correia quickly converges to CA In two words homogeneous state von Neumann’s model Heterogeneous or Periodic - Class II Properties of CA Wolfram classification quickly converges to a Life constant structure or periodic Chaotic - Class III Irregular and long term unpredictable Complex - Class IV Irregular repetition with complex interactions  Classes by Wolfram Cellular Automata Homogeneous or Fixed Point - Class I Luı́s Correia quickly converges to CA In two words homogeneous state von Neumann’s model Heterogeneous or Periodic - Class II Properties of CA Wolfram classification quickly converges to a Life constant structure or periodic Chaotic - Class III Irregular and long term unpredictable Complex - Class IV Irregular repetition with complex interactions  Classes by Wolfram Cellular Automata Homogeneous or Fixed Point - Class I Luı́s Correia quickly converges to CA In two words homogeneous state von Neumann’s model Heterogeneous or Periodic - Class II Properties of CA Wolfram classification quickly converges to a Life constant structure or periodic Chaotic - Class III Irregular and long term unpredictable Complex - Class IV Irregular repetition with complex interactions  Class I Cellular Automata Luı́s Correia CA In two words von Neumann’s model Properties of CA Wolfram classification Life  Class II 1st Cellular Automata Luı́s Correia CA In two words von Neumann’s model Properties of CA Wolfram classification Life  Class II 2nd Cellular Automata Luı́s Correia CA In two words von Neumann’s model Properties of CA Wolfram classification Life  Class III Cellular Automata Luı́s Correia CA In two words von Neumann’s model Properties of CA Wolfram classification Life  Class IV 1st Cellular Automata Luı́s Correia CA In two words von Neumann’s model Properties of CA Wolfram classification Life  Class IV 2nd Cellular Automata Luı́s Correia CA In two words von Neumann’s model Properties of CA Wolfram classification Life  Life game - description Cellular Automata Luı́s Correia Proposed by John Conway ∼ 1970 CA CA In two words von Neumann’s model 2D Properties of CA square geometry Wolfram classification Moore neighbourhood Life Rule Survival: A cell survives if it has 2 or 3 alive neighbours Birth: A cell is born if it has exactly 3 alive neighbours Death: A cell dies, by overcrowding, if it has 4 or more alive neighbours, and by isolation, if it has 0 or 1 alive neighbour  Life properties Cellular Automata Luı́s Correia CA Totalising rule In two words von Neumann’s model outcome only depends on the number of active neighbours Properties of CA and not on their position Wolfram classification Life Very rich behaviour Universal computing power (Turing machine) Many variants (but less interesting) Life alive in CAS  Disclaimer Cellular Automata Luı́s Correia CA In two words von Neumann’s model All 1D CA and Life images shown are not Self-Organisation! Properties of CA Wolfram classification Updating discipline is synchronous Life ⇒ instantaneous propagation at distance (of the synchronisation signal)  asynchronism Cellular Automata mild forms of asynchronism are more realistic Luı́s Correia CA asynchronous cell update: In two words von Neumann’s model in each iteration cells are updated with probability Properties of CA α ∈ [0, 1] Wolfram classification smooth transition from synchronism (α = 1) Life small decrease in α from 1 changes significantly behaviour of CA most become type 1 or random (type 3??) other forms of synchronism sequential (less realistic): fixed, random fair & unfair randomised: next update randomised for each cell e.g. N (µ, σ)