* Η ταινία: Η ταινία της μηχανής Turing χρησιμεύει ως κύριο μέσο αποθήκευσης και εισόδου/εξόδου. Η ακολουθία εισόδου είναι αρχικά γραμμένη στην ταινία. Η υπόλοιπη ταινία (ενδεχομένως άπειρη σε μήκος) είναι αρχικά γεμάτο με κενά σύμβολα.
* Η κεφαλή ανάγνωσης/εγγραφής: Η κεφαλή μπορεί να διαβάσει το σύμβολο στην τρέχουσα θέση του στην ταινία, να γράψει ένα νέο σύμβολο στην ταινία στην τρέχουσα θέση του και να μετακινήσει μία θέση προς τα αριστερά ή δεξιά.
* Το μητρώο κατάστασης: Αυτό κατέχει την τρέχουσα κατάσταση της μηχανής Turing. Η κατάσταση αντιπροσωπεύει τη "μνήμη" του μηχανήματος για το τι έχει κάνει μέχρι τώρα.
* Η λειτουργία μετάβασης (ή ο πίνακας): Αυτή είναι η καρδιά της λογικής της μηχανής Turing. Υπαγορεύει τη συμπεριφορά του μηχανήματος με βάση την τρέχουσα κατάσταση και το σύμβολο που βρίσκεται επί του παρόντος κάτω από την κεφαλή ανάγνωσης/εγγραφής. Η λειτουργία μετάβασης εκφράζεται τυπικά ως σύνολο κανόνων ή πίνακα που χαρτογραφεί (τρέχουσα κατάσταση, τρέχον σύμβολο) σε (νέα κατάσταση, νέο σύμβολο για να γράψει, κατεύθυνση για να μετακινηθεί).
Πώς λειτουργεί-βήμα προς βήμα:
1. Αρχικοποίηση:
* Η ακολουθία εισόδου είναι γραμμένη στην ταινία.
* Η κεφαλή ανάγνωσης/εγγραφής τοποθετείται στην αρχή της ακολουθίας εισόδου (συνήθως το αριστερό σύμβολο).
* Το μηχάνημα ξεκινά σε μια καθορισμένη "κατάσταση εκκίνησης".
2. επανάληψη: Το μηχάνημα Turing εκτελεί επανειλημμένα τα παρακάτω βήματα:
* Διαβάστε: Η κεφαλή ανάγνωσης/εγγραφής διαβάζει το σύμβολο στην τρέχουσα θέση του στην ταινία.
* αναζήτηση: Το μηχάνημα εξετάζει το ζεύγος (τρέχουσα κατάσταση, τρέχον σύμβολο) στη λειτουργία μετάβασης. Η λειτουργία μετάβασης παρέχει τρεις πληροφορίες:
* Νέα κατάσταση: Το μηχάνημα μεταβαίνει σε μια νέα κατάσταση.
* Νέο σύμβολο: Το μηχάνημα γράφει ένα νέο σύμβολο στην ταινία στην τρέχουσα θέση (αντικαθιστώντας το παλιό σύμβολο). Αυτό μπορεί να είναι το ίδιο με το παλιό σύμβολο, αφήνοντας αποτελεσματικά το αμετάβλητο.
* κατεύθυνση: Το μηχάνημα μετακινεί την κεφαλή ανάγνωσης/εγγραφής μία θέση προς τα αριστερά ή δεξιά στην ταινία.
* Ενημέρωση: Το μηχάνημα ενημερώνει το μητρώο της κατάστασης με τη νέα κατάσταση. Στη συνέχεια μετακινεί την κεφαλή ανάγνωσης/εγγραφής σύμφωνα με την καθορισμένη κατεύθυνση και γράφει το νέο σύμβολο.
3.
* Το μηχάνημα συνεχίζει να επαναλαμβάνει μέχρι να συμβεί ένα από τα δύο πράγματα:
* κατάσταση διακοπής: Η λειτουργία μετάβασης μπορεί να καθορίσει μια "κατάσταση διακοπής". Όταν το μηχάνημα εισέλθει σε κατάσταση διακοπής, σταματά να εκτελεί. Οι καταστάσεις αναστολής μπορούν να "αποδοθούν" ή να "απορρίψουν", ανάλογα με το επιθυμητό αποτέλεσμα.
* Δεν υπάρχει μετάβαση: Μπορεί να μην υπάρχει καθορισμένη μετάβαση για τον τρέχοντα συνδυασμό (σύμβολο, σύμβολο). Αυτό αναγκάζει επίσης να σταματήσει το μηχάνημα.
Διαχείριση διαφορετικών ακολουθιών εισόδου:
Η μηχανή Turing αποτελεσματικά * επεξεργάζεται * την ακολουθία εισόδου με βάση τη λειτουργία μετάβασης. Η λειτουργία μετάβασης έχει σχεδιαστεί για να εκτελεί κάποια συγκεκριμένη εργασία, όπως:
* Αναγνωρίζοντας μια γλώσσα: Ο καθορισμός του εάν μια ακολουθία εισόδου ανήκει σε μια προκαθορισμένη γλώσσα. Για παράδειγμα, θα μπορούσε να ελέγξει εάν μια συμβολοσειρά περιέχει έναν ίσο αριθμό '0 και' 1. Το μηχάνημα θα σταματούσε σε κατάσταση αποδοχής εάν η συμβολοσειρά ανήκει στη γλώσσα και μια κατάσταση απόρριψης διαφορετικά.
* Μετασχηματισμός μιας εισόδου: Μετατροπή της ακολουθίας εισόδου σε διαφορετική ακολουθία εξόδου. Για παράδειγμα, θα μπορούσε να εκτελέσει προσθήκη, αφαίρεση ή λογικές λειτουργίες. Η έξοδος θα παραμείνει στην ταινία όταν σταματά το μηχάνημα.
* ταξινόμηση: Διακανονισμός της ακολουθίας εισόδου σε συγκεκριμένη σειρά.
* Προσομοίωση: Προσομοιώστε τη συμπεριφορά ενός άλλου μηχανήματος Turing ή υπολογιστικού συστήματος.
Παράδειγμα (απλοποιημένη αναγνώριση γλώσσας):
Ας υποθέσουμε ότι θέλουμε μια μηχανή Turing να αναγνωρίσει τη γλώσσα όλων των χορδών που αποτελούνται μόνο από το 1. Η λειτουργία μετάβασης μπορεί να μοιάζει με αυτό:
* δηλώστε A (κατάσταση εκκίνησης):
* Εάν διαβάσετε '1', γράψτε '1', μετακινήστε δεξιά, μεταβείτε στο κράτος Α.
* Εάν διαβάσετε κενό ('b'), γράψτε 'b', μετακινήστε δεξιά, μεταβείτε στην αποδοχή του κράτους.
* Εάν διαβάσετε '0', γράψτε '0', μετακινήστε δεξιά, πηγαίνετε στο κράτος απορρίπτεται.
* Κατάσταση αποδοχή: Σταματήστε και αποδεχτείτε.
* Απόρριψη κατάστασης: Σταματήστε και απορρίψτε.
Εάν η είσοδος είναι "111", το μηχάνημα θα:
1. Ξεκινήστε στην κατάσταση Α, διαβάστε '1', γράψτε '1', μετακινήστε δεξιά, πηγαίνετε στο κράτος Α.
2. Ξεκινήστε στην κατάσταση Α, διαβάστε '1', γράψτε '1', μετακινήστε δεξιά, πηγαίνετε στο κράτος Α.
3. Ξεκινήστε στην κατάσταση Α, διαβάστε '1', γράψτε '1', μετακινήστε δεξιά, πηγαίνετε στο κράτος Α.
4. Ξεκινήστε στην κατάσταση Α, διαβάστε «Β», γράψτε «Β», μετακινήστε δεξιά, πηγαίνετε στο κράτος Αποδοχή.
5. Σταματήστε να αποδεχτείτε την κατάσταση.
Εάν η είσοδος είναι "101", το μηχάνημα θα:
1. Ξεκινήστε στην κατάσταση Α, διαβάστε '1', γράψτε '1', μετακινήστε δεξιά, πηγαίνετε στο κράτος Α.
2. Ξεκινήστε στην κατάσταση Α, διαβάστε '0', γράψτε '0', μετακινήστε δεξιά, πηγαίνετε στο κράτος απόρριψη.
3. Σταματήστε να απορρίψετε την κατάσταση.
Βασικές έννοιες:
* ντετερμινισμός: Συνηθέστερα, τα μηχανήματα Turing είναι ντετερμινιστικά. Αυτό σημαίνει ότι για κάθε ζευγάρι (κατάσταση, σύμβολο), υπάρχει μόνο μία καθορισμένη μετάβαση. Οι μη-καθοριστικές μηχανές Turing (NDTMs) επιτρέπουν πολλαπλές μεταβάσεις, αλλά θεωρητικά ισοδυναμούν με τις ντετερμινιστικές μηχανές Turing.
* Power: Το μηχάνημα Turing είναι ένα ισχυρό θεωρητικό μοντέλο υπολογισμού. Μπορεί να προσομοιώσει οποιονδήποτε αλγόριθμο που μπορεί να εκτελεστεί σε έναν ψηφιακό υπολογιστή.
* Περιορισμοί: Ενώ οι θεωρητικά ισχυρές, οι μηχανές Turing είναι πολύ χαμηλού επιπέδου και κουραστικά για να προγραμματίσουν άμεσα. Οι πιο πρακτικές γλώσσες προγραμματισμού και αρχιτεκτονικές αφηρημένες τις λεπτομέρειες των μεταβάσεων της ταινίας, της κεφαλής και του κράτους. Ωστόσο, η κατανόηση του υποκείμενου μοντέλου μηχανής Turing βοηθά στην κατανόηση των θεμελιωδών ορίων του υπολογισμού.
Συνοπτικά, ένα μηχάνημα Turing χειρίζεται διαφορετικές διαμορφώσεις αλληλουχίας με συστηματική ανάγνωση, γραφή και κίνηση στην ταινία του, καθοδηγούμενη από τη λειτουργία μετάβασης και το μητρώο κατάστασης. Η λειτουργία μετάβασης έχει σχεδιαστεί προσεκτικά για να εκτελεί έναν συγκεκριμένο υπολογισμό στην ακολουθία εισόδου, επιτρέποντας στο μηχάνημα να αποδεχθεί, να απορρίψει ή να μετατρέψει την είσοδο με βάση τα χαρακτηριστικά του.
Πνευματικά δικαιώματα © Γνώση Υπολογιστών Όλα τα δικαιώματα κατοχυρωμένα