Die Webseiten der Fachschaft Informatik am ERG Saalfeld


nicht entscheidbar

Wie schon auf der Seite zur Entscheidbarkeit angegeben, gibt es Ja-Nein-Fragen, die weder mit 'ja' noch mit 'nein' beantwortet werden können. Diese Fragen nennen wir nicht entscheidbar.



Game of Life

Es soll jetzt das Spiel des Lebens (Game of Life) von John Conway als ein Beispiel für ein nicht entscheidbares Problem erläutert werden.
 

Das Spielfeld

Das Spielfeld ist in Zeilen und Spalten unterteilt und im Idealfall unendlich groß. Jedes Gitterquadrat ist eine Zelle, die einen von zwei Zuständen einnehmen kann, welche als lebendig bzw. tot bezeichnet werden. Jede lebende oder tote Zelle hat auf diesem Spielfeld genau acht Nachbarzellen. Die nächste Generation ergibt sich durch die Befolgung der folgenden Regeln.

Die Spielregeln

Die Folgegeneration wird für alle Zellen gleichzeitig berechnet ("Glockenschlag") und ersetzt die aktuelle Generation.

  • Eine tote Zelle mit genau drei lebenden Nachbarn wird in der Folgegeneration neu geboren.
  • Lebende Zellen mit weniger als zwei lebenden Nachbarn sterben in der Folgegeneration an Einsamkeit.
  • Eine lebende Zelle mit zwei oder drei lebenden Nachbarn bleibt in der Folgegeneration am Leben.
  • Lebende Zellen mit mehr als drei lebenden Nachbarn sterben in der Folgegeneration an Überbevölkerung.

Beispiel:

Ausgangszustand 1. Glockenschlag 2. Glockenschlag 3. Glockenschlag


Problem:

Man kann zeigen, dass es keinen Algorithmus gibt, der als Eingabe zwei beliebige Game-of-Life-Konfigurationen erhält und in allen Fällen entscheiden kann, ob eine Konfiguration aus der anderen entstehen kann oder nicht. Diese Frage ist damit unentscheidbar. (Quelle: siehe Weblink 2)

 

Aufgaben

  1. Erzeugen Sie von dem angegebenen Beispiel per Hand die nächsten 2 Populationen.
  2. Überprüfen Sie Ihre angegebenen Populationen aus Aufgabe 1 in der Online-Simulation (siehe Weblink 1)
  3. Informieren Sie sich über spezielle Populationen wie Raumschiffe, Gleiter und Puffer. Informieren Sie sich auch über das Hacker-Emblem. (siehe Weblink 2)

 

Weblinks

  1. bitstorm.org/gameoflife/
  2. de.wikipedia.org/wiki/Conways_Spiel_des_Lebens
  3. beltoforion.de/article.php?a=game_of_life&hl=de

 

zurück


© ERG Saalfeld   -   Hans-Dietrich Kirmse   25.03.2019