Τι είναι μια αφηρημένη μηχανή;

Οι αφηρημένες μηχανές, που ονομάζονται επίσης αυτόματα, αποτελούν στοιχείο της θεωρητικής επιστήμης των υπολογιστών.Μια αφηρημένη μηχανή μοιάζει με μια λειτουργία στα μαθηματικά.Λαμβάνει εισροές και παράγει εξόδους σύμφωνα με συγκεκριμένους κανόνες.Τα αφηρημένα μηχανήματα διαφέρουν από πιο κυριολεκτικά μηχανήματα, επειδή θεωρούνται ότι λειτουργούν τέλεια και ανεξάρτητα από το υλικό.Υποδιαιρούνται σε τύπους με βάση τα χαρακτηριστικά όπως ο τρόπος με τον οποίο εκτελούν τις λειτουργίες τους και ποιοι τύποι εισροών μπορούν να λάβουν.οποιοδήποτε δεδομένο σημείο.Μια αφηρημένη μηχανή ονομάζεται ντετερμινιστική εάν υπάρχει πάντα μόνο ένας τρόπος για να προχωρήσει.Είναι μη -nondeterministic εάν υπάρχουν πολλαπλές δυνατότητες για το μηχάνημα σε τουλάχιστον μία από τις πιθανές καταστάσεις του.Ένα automaton pushdown είναι αυτό που έχει την ικανότητα να χειριστεί τη στοίβα των εισροών, αντί να ανταποκρίνεται απλά σε αυτά ένα προς ένα με τη σειρά με την οποία εμφανίζονται. "Το Wolfram Mathworld

δίνει δύο διάσημα παραδείγματα αφηρημένων μηχανών.Ένα από αυτά τα παραδείγματα είναι το Conways Game of Life, το οποίο είναι μια ντετερμινιστική αφηρημένη μηχανή, επειδή μόνο μία διαμόρφωση μπορεί να βγει από οποιοδήποτε άλλο.Αυτό το παιχνίδι χρησιμοποιεί ένα πλέγμα στο οποίο κάθε κουτί, ή κελί, μπορεί είτε να έχει την κατάσταση που ζει είτε να πεθάνει.Η κατάσταση ολόκληρου του δικτύου καθορίζεται με βάση την προηγούμενη κατάσταση.Εάν ένα ζωντανό κύτταρο αγγίζει ακριβώς δύο ή τρία άλλα ζωντανά κύτταρα, συνεχίζει να ζει.Εάν έχει ένα, δύο ή περισσότερους από τρεις γείτονες (μέχρι και οκτώ), πεθαίνει.Ένα νεκρό κελί με ακριβώς τρεις γείτονες θα ζωντανεύει.Διαφορετικά, θα παραμείνει νεκρός.

Ένα άλλο παράδειγμα, η μηχανή Turing, είναι ένα από τα πιο βασικά και θεμελιώδη αφηρημένα μηχανήματα στην επιστήμη των υπολογιστών.Μια μηχανή Turing εκτελεί λειτουργίες σε μια ταινία mdash; μια σειρά συμβόλων mdash; του απεριόριστου μεγέθους.Περιέχει οδηγίες τόσο για την αλλαγή των συμβόλων όσο και για την αλλαγή του συμβόλου πάνω στο οποίο λειτουργεί.Ένα απλό μηχάνημα Turing μπορεί να έχει μόνο το σύμβολο μετασχηματισμού οδηγίας στο 1, στη συνέχεια να μετακινηθεί δεξιά.Αυτό το μηχάνημα δεν θα έδινε τίποτα άλλο από μια σειρά 1s.Αυτή η απλή μηχανή Turing είναι ντετερμινιστική, αλλά είναι επίσης δυνατή η κατασκευή μη -μηδενιστικών μηχανών Turing που μπορούν να εκτελέσουν αρκετές διαφορετικές λειτουργίες, δεδομένης της ίδιας εισόδου.

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