cursus Inleiding Adaptieve Systemen Opleiding Kunstmatige Intelligentie 2020-21

Hoorcollege

Cellulaire Automaten

Kennen

  • Redenen om CA's te bestuderen.
  • Conway's game of life (GOL).
  • De notie totalitaire CA; GOL is totalitair.
  • Von Neumann omgeving vs. Moore omgeving (“Moore is meer”). Analogieën van deze omgevingen in hogere dimensies.
  • Stabiliteit vs. periodiciteit vs. non-periodiciteit (zich manifesterende in ruis en chaos). Overgangsfase.
  • Argumenten voor de onvermijdelijkheid van stabiliteit danwel periodiciteit in eindige omgevingen.
  • König's lemma.
  • De notie convergente deelrij (ook wel: limietpunt of verdichtingspunt of ophopingspunt). **** dictaat ***
  • De stelling van Jarkko Kari dat elke ontwikkeling van een CA een verdichtingspunt bezit; het bewijs van deze stelling zoals die op het college besproken is.
  • Stroom, pulsklok en logische schakelingen (en, of, nand, nor, xor, niet) in GOL.
  • Conway's game of life is Turing-volledig. Consequenties van dit feit, met als belangrijkste bijvoorbeeld dat geen programma kan worden geschreven dat van een willekeurige GOL-configuratie kan bepalen of deze stopt.
  • Een conceptueel eenvoudiger Turing-volledige CA: Wire world.
  • Mogelijke randidentificaties van een 2D CA: rechthoek, cilinder, torus (Netlogo); fles van Klein, Möbius band, projectief vlak. Consequenties van randidentificaties; wisseling van oriëntatie.
  • Variaties op GOL: meer toestanden per cel, andere connectiviteit, andere timing van updates, non-deterministische toestandovergangen; eenvoudige voorbeelden van probabilistische CA's zoals infectie- en bosbrandmodellen.
  • Eigenschappen van een CA: discreet in ruimte en tijd; homogeen in ruimte en tijd; lokaal gedefinieerd.
  • Eén-dimensionale CA's; de parameters K, N, en R. De 2D-visualizatie van de progressie van een 1D-CA.
  • Wolframcodering van een 1D CA; de Turing-volledigheid van de 1D CA met code 110.
  • Langton's λ-parameter, en het verband met Wolfram's klassenindeling. Langton's indeling van de regelruimte; de sweet spot in deze regelruimte: Wolfram's klasse IV.
  • Wolfram's klassenindeling van 1D CA's. Met stijgende λ: stabiel (I) → periodiek (II) → complex (IV) → chaos (III). Dus de nummering gaat van stabiel naar complex./LI>
  • (Tijd-)reversibiliteit van CA's; een CA is reversibel a.e.s.a. de regelverzameling injectief is.
  • Reversibiliteit is beslisbaar voor 1D CA's maar niet voor 2D CA's. GOL is niet reversibel. Margolus' gasautomaat is reversibel. (Netlogo: model “Lattice Gas Automaton”.)
  • Hof van Eden (weespatroon). Een CA bevat een weespatroon a.e.s.a. de regelverzameling niet surjectief is. GOL bevat weespatronen.
  • Kunnen

  • Beweringen toetsen t.a.v. eenvoudige configuraties van Conway's game of life, bijvoorbeeld t.a.v. het raken van een veld, periodiciteit van patronen, of stoppen. (I.h.a. is zo'n check natuurlijk onbeslisbaar, vandaar het voorvoegsel “eenvoudig”.)
  • Von Neumann- en Moore omgevingen beschrijven in hogere dimensies.
  • König's lemma bewijzen.
  • Het bewijs van de stelling van Jarkko Kari zoals dat op het college besproken is reproduceren.
  • Het aantal mogelijke regelverzamelingen, en de grootte van één regelverzameling van een CA bepalen aan de hand van parameters K, N en R.
  • Het aantal mogelijke regelverzamelingen, en de grootte van één regelverzameling van een totalitaire CA (zoals GOL) bepalen.
  • Een Wolfram-codering geven van een 1D CA; een Wolfram-codering interpreteren.
  • Het gedrag van een Wolfram-klasse (I, II, III of IV) omschrijven.
  • Het gedrag van een turmite zoals Langton's mier of een zg. node count learner vertalen naar een CA-regelverzameling.
  • Materiaal

  • Slides Cellulaire Automaten.
  • TCBoN H15.
  • Dictaat Marco Wiering H2.
  • Handouts Marco Wiering 2007 “ALife”.
  • Werkcollegedictaat.

  • Laatst gewijzigd op dinsdag 26 januari 2021, om 17:48 uur ——— translate to ru, ro, or en ——— commentaar welkom