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

Γενικά

Τα κυτταρικά αυτόματα εισήχθησαν και μελετήθηκαν κατ' αρχήν στη δεκαετία του 1960 από τον Ούγγρο μαθηματικό John von Neumann που ερευνούσε την ύπαρξη και τις ιδιότητες μοντέλων "αυτομάτων" που έχουν την ιδιότητα της αναπαραγωγής, δηλαδή της παραγωγής αντιγράφων.

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


Σχήμα 1. Χαρακτηριστικοί τύπου κυτταρικών αυτομάτων είναι τα μονοδιάστατα, τα διδιάστατα και τα εξαγωνικά κυτταρικά αυτόματα, όπου κάθε κύτταρο εξαρτάται από τα 2, 8, 6 γειτονικά του, αντίστοιχα, όπως φαίνεται στο σχήμα.

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

"Εάν όλα τα γειτονικά κύτταρα είναι στην κατάσταση 0, μεταβαίνω στην κατάσταση 0".

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

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

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

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

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

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

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


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


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


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

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

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


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

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

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

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


Τελευταία ενημέρωση 23 Μαρτίου 2015.
Στείλτε μου mail (etzafestas@phs.uoa.gr)