Κυτταρικά αυτόματα και το παιχνίδι της ζωής

Γενικά

Τα κυτταρικά αυτόματα είναι δομές που μοντελοποιούν τη συμπεριφορά κατανεμημένων συστημάτων με συγκεκριμένη χωρική (γεωμετρική) διάταξη. Ονομάζονται "κυτταρικά" επειδή είναι εμπνευσμένα από κυτταρικές διατάξεις όπου κάθε κύτταρο αλληλεπιδρά με τα γειτονικά του στο χώρο και είναι "αυτόματα" επειδή η συμπεριφορά κάθε κυττάρου είναι πλήρως καθορισμένη από το αντίστοιχο μοντέλο, άρα "αυτόματη" (βλέπε σχήμα 1).

Εσωτερικά, το κάθε κύτταρο έχει ένα συγκεκριμένο αριθμό δυνατών καταστάσεων και μία μηχανή μετάβασης από κατάσταση σε κατάσταση. Π.χ. για ένα κυτταρικό αυτόματο όπου τα κύτταρα μπορούν να έχουν δύο καταστάσεις, 0 ή 1, μία μηχανή μετάβασης μπορεί να περιλαμβάνει έναν ή περισσότερους κανόνες του τύπου

Η χωρική διάταξη ενός κυτταρικού αυτομάτου προσδιορίζει σχεδόν μονοσήμαντα τις εξαρτήσεις κυττάρων από κύτταρα, αφού κάθε κύτταρο εξαρτάται από τα γειτονικά του (βλ. σχήμα 1). Σε πιο προχωρημένα μοντέλα, ένα κύτταρο μπορεί να εξαρτάται από πιο απομακρυσμένους γείτονες (π.χ. ένα κύτταρο ενός μονοδιάστατου κυτταρικού αυτομάτου να "βλέπει" δύο θέσεις δεξιά και τρεις αριστερά), να έχει μνήμη που καθορίζει το βαθμό εξάρτησής του (π.χ. ένα κύτταρο ενός διδιάστατου κυτταρικού αυτομάτου να παύει να βλέπει κάποιο γειτονικό κύτταρο, όταν εκείνο έχει βρεθεί συνεχώς σε μία ορισμένη κατάσταση) κ.ο.κ.

Η συμπεριφορά όλων των κυττάρων ενός κυτταρικού αυτομάτου είναι η ίδια, ενώ σε πιο προχωρημένα μοντέλα μπορεί να χρησιμοποιούνται μεταβλητές μνήμης που διαφοροποιούν τα κύτταρα ανάλογα με το περιβάλλον και την αρχική κατάσταση του καθενός.

Ενα διδιάστατο ΚΑ αποτελείται από:

• έναν διδιάσταστο πίνακα από κύτταρα
• ένα σύνολο κανόνων μετάβασης των κυττάρων

Το παιχνίδι της ζωής

Πρόκειται για το πλέον γνωστό διδιάστατο κυτταρικά αυτόματο, επινοήθηκε από τον John Conway (δεκαετία 1960), και βασίζεται στους παρακάτω κανόνες μετάβασης. Μετράμε γειτονιές 8 θέσεων (τα διπλανά και διαγώνια στοιχεία μίας θέσης). Κάθε κύτταρο έχει μόνο δύο καταστάσεις (ζωή - θάνατος)
Οι κανόνες μετάβασης από κατάσταση σε κατάσταση ανάλογα με τον αριθμό των ζωντανών γειτόνων είναι:

• Αν ένα ζωντανό κύτταρο έχει κάτω από 2 (ζωντανούς) γείτονες, πεθαίνει από μοναξιά
• Αν ένα ζωντανό κύτταρο έχει πάνω από 3 (ζωντανούς) γείτονες, πεθαίνει από υπερπληθυσμό
• Αν ένα ζωντανό κύτταρο έχει ακριβώς 2 (ζωντανούς) γείτονες, συνεχίζει να ζεί
• Αν ένα νεκρό κύτταρο έχει ακριβώς 3 (ζωντανούς) γείτονες, γεννιέται.

Σχήμα 2. Στατικοί ή ακίνητοι σχηματισμοί στο παιχνίδι της ζωής

Σχήμα 3. Περιοδικοί σχηματισμοί στο παιχνίδι της ζωής (περίοδος 2 βημάτων)

Σχήμα 4. Μετακινούμενοι σχηματισμοί στο παιχνίδι της ζωής

Συνήθεις συμπληρωματικές δυνατότητες κυτταρικών αυτομάτων είναι οι εξής:

• Κυκλικό κυτταρικό αυτόματο. Στο αυτόματο αυτό, θεωρείται ότι ένα συνοριακό κύτταρο δε βλέπει "τοίχο", αλλά γειτονεύει με το αντίστοιχο κύτταρο από τη συμμετρική πλευρά. Π.χ. ένα κύτταρο στην τελευταία δεξιά στήλη, δε βλέπει τοίχο στα δεξιά του αλλά βλέπει το κύτταρο της πρώτης στήλης στην ίδια γραμμή. Δηλαδή το σχήμα αποτελεί ένα γεωμετρικό torus (toroidal κυτταρικό αυτόματο).
• Κυτταρικό αυτόματο με στατιστικό θόρυβο. Στο αυτόματο αυτό, οι κανόνες μετάβασης "παρενοχλούνται" από μία πηγή θορύβου, δηλαδή με κάποια παράμετρο πιθανότητας (ποσοστό θορύβου), η επόμενη κατάσταση ενός κυττάρου αντιστρέφεται (από μαύρο σε άσπρο και αντίστροφα).
• Ασύγχρονο κυτταρικό αυτόματο. Στο αυτόματο αυτό, τα κύτταρα δεν μεταβαίνουν στην επόμενη κατάστασή τους παράλληλα (σύγχρονα), αλλά σειριακά (ασύγχρονα), δηλαδή ένα-ένα. Αυτό σημαίνει ότι ένα κύτταρο μπορεί να επηρεασθεί από την κατάσταση ενός γειτονικού κυττάρου που άλλαξε ήδη τιμή πιο γρήγορα.
• Κυτταρικό αυτόματο με μόνιμη "πηγή ζωής", π.χ. με "ζωντανά σύνορα". Στο αυτόματο αυτό, θεωρείται ότι ένα συνοριακό κύτταρο δε βλέπει "τοίχο", αλλά γειτονεύει με ζωντανό κύτταρο στην αντίστοιχη θέση, π.χ. ένα κύτταρο στην τελευταία δεξιά στήλη, δε βλέπει τοίχο στα δεξιά του αλλά βλέπει ένα ζωντανό κύτταρο (που παραμένει αθάνατο!).
• Κυτταρικά αυτόματα με μνήμη ή/και με πιο σύνθετους κανόνες. Αλλες παραλλαγές κυτταρικών αυτομάτων χρησιμοποιούν μνήμη ή/και πιο σύνθετους κανόνες μετάβασης, π.χ. κανόνες που χρησιμοποιούν ως δεδομένα όχι μόνο τον αριθμό των ζωντανών γειτονικών κυττάρων, αλλά και την προηγούμενη κατάσταση του ίδιου του κυττάρου.

Τέλος, άλλα πιο πολύπλοκα και ενδιαφέροντα διδιάστατα κυτταρικά αυτόματα μπορούν να κατασκευασθούν με τη βοήθεια γενικευμένων ποιοτικών κανόνων, με προσθήκη συναρτήσεων προσαρμογής ή εξειδίκευσης κ.ο.κ.

Υλοποίηση της πλατφόρμας

Εγχειρίδιο χρήσης

• Το ρολόι του συστήματος.

• Τρία κουμπιά ελέγχου της προσομοίωσης.

  Το κουμπί Start/Stop συνεχίζει/παγώνει την προσομοίωση και σε κάθε βήμα της προσομοίωσης εκτελεί όλα τα κύτταρα από μία φορά (σύγχρονα ή ασύγχρονα, ανάλογα με την τρέχουσα επιλογή). Το κουμπί Step προχωρά την προσομοίωση κατά ένα μόνο βήμα. Τέλος, το κουμπί Restart επανεκκινεί την προσομοίωση, δηλαδή αρχικοποιεί το ρολόι στο 0 και κάνει reset τα κύτταρα και τους συλλογείς των στατιστικών δεδομένων.

• Τρία κουμπιά σχετικά με το τρέχον περιβάλλον ή πείραμα (context).

  Τα τρία κουμπιά (View, Save, Retrieve) επιτρέπουν αντίστοιχα την επισκόπηση, αποθήκευση και ανάκτηση της τρέχουσας κατάστασης του κυτταρικού αυτομάτου. Επειδή το αυτόματο είναι μεγάλου μεγέθους (120x120 θέσεων), δεν εμφανίζεται αναλυτικά το περιεχόμενο των κυττάρων κατά την επισκόπηση (View). Κατά την αποθήκευση (Save), η τρέχουσα κατάσταση αποθηκεύεται εσωτερικά στο πρόγραμμα και μπορεί οποτεδήποτε να ανακτηθεί με το κουμπί Retrieve. Αυτή η δυνατότητα επιτρέπει την επανάληψη ενός πειράματος: ένα πείραμα μπορεί να επαναληφθεί στις ίδιες ακριβώς συνθήκες, εάν αρχικά γίνει αποθήκευση, εκτελεσθεί το πείραμα και εν συνεχεία γίνει ανάκληση και επανεκτέλεση. Σε αυτή την περίπτωση οι καμπύλες των αποτελεσμάτων θα δείχνουν τα δύο διαδοχικά πειράματα. Προφανώς, η επανάληψη μπορεί να γίνει όσες φορές επιθυμεί ο χρήστης.

• Συνιστώσες ελέγχου των παραμέτρων του κυτταρικού αυτομάτου.
  • Asynchronous. Ενεργοποιεί/απενεργοποιεί το ασύγχρονο κυτταρικό αυτόματο.
  • Live boundaries. Ενεργοποιεί/απενεργοποιεί το κυτταρικό αυτόματο με "ζωντανά σύνορα".
  • 8 neighbours. Ενεργοποιεί/απενεργοποιεί το κυτταρικό αυτόματο 8 γειτόνων, όπου ένα κύτταρο λαμβάνει υπόψη και τους 8 γείτονες, ή μόνον τους 4 (πάνω,κάτω,αριστερά,δεξιά).
  • Toroidal. Ενεργοποιεί/απενεργοποιεί το κυκλικό κυτταρικό αυτόματο.
  • Noisy. Ενεργοποιεί/απενεργοποιεί την ύπαρξη θορύβου (με 2% πιθανότητα, η κατάσταση ενός κυττάρου γίνεται αντιληπτή εσφαλμένα, δηλαδή 1 αντί 0 ή 0 αντί 1).
  • Rule. Ενεργοποιεί/απενεργοποιεί τη χρήση ενός αυθαίρετου κανόνα για το κυτταρικό αυτόματο, που μπορεί να διαφέρει για την περίπτωση αυτομάτου 8-γειτόνων και 4-γειτόνων. Ο προ-προγραμματισμένος κανόνας στο κυτταρικό αυτόματο είναι αυτός του παιχνιδιού της ζωής. Ο "αυθαίρετος" κανόνας που χρησιμοποιείται εφόσον ενεργοποιηθεί είναι κατ' αρχήν ο ίδιος κανόνας του κυτταρικού αυτομάτου και μπορεί να αλλαχθεί με τη βοήθεια του κουμπιού Edit που ανοίγει τον επεξεργαστή του παρακάτω σχήματος. Για καθεμία από τις περιπτώσεις 4 ή 8 γειτόνων ορίζεται η έξοδος του κανόνα ανάλογα με τον αριθμό των ζωντανών γειτόνων (0-4 στην περίπτωση του αυτομάτου 4 γειτόνων και 0-8 στην περίπτωση του αυτομάτου 8 γειτόνων). Η έξοδος ορίζεται ως 1 ή 0 όταν είναι επιλεγμένη ή αποεπιλεγμένη, αντίστοιχα. Στην παρακάτω εικόνα φαίνεται ο κανόνας του τυπικού παιχνιδιού της ζωής.
    

• Συνιστώσες παρουσίασης στατιστικών δεδομένων.

  Η λίστα των "simulation observers" παρουσιάζει τα ονόματα των συλλογέων στατιστικών δεδομένων. Εδώ πρόκειται για έναν μόνον συλλογέα που καταγράφει το μέσο όρο των ζωντανών κυττάρων (με τιμή 1) κάθε χρονική στιγμή. Το κουμπί Show επιτρέπει την εμφάνιση της αντίστοιχης καμπύλης. Στην επόμενη εικόνα δίνεται ένα παράδειγμα εξέλιξης του πληθυσμού των ζωντανών κυττάρων στο χρόνο. Οπως φαίνεται, το ποσοστό των ζωντανών κυττάρων σταθεροποιείται στο χρόνο.
  Κάποιες γενικές διευκρινίσεις σχετικά με την εμφάνιση στατιστικών δεδομένων δίνονται εδώ.

  

• Υπόλοιπες συνιστώσες ελέγχου.

  Το κουμπί Randomize επιτρέπει την τυχαία αρχικοποίηση όλων των κυττάρων (0 ή 1). Το κουμπί Clear επιτρέπει την αρχικοποίηση όλων των κυττάρων με την τιμή 0. Οι άλλες συνιστώσες δεν χρησιμοποιούνται.

Οι δυνατότητες αυτές της πλατφόρμας επιτρέπουν στο χρήστη να πειραματισθεί συστηματικά με διάφορες παραλλαγές κυτταρικών αυτομάτων, με αρχικές συνθήκες και παραμετροποίηση της επιλογής του.