Στη μηχανή Turing του σχήματος αρχική κατάσταση είναι η q και τελική κατάσταση είναι η h. Τα σύμβολα της ταινίας είναι τα 0, 1 και □, όπου □ είναι το σύμβολο του κενού. Το R σημαίνει ότι η κεφαλή εκτελεί κίνηση προς τα δεξιά και το L προς τα αριστερά. Οι μεταβάσεις σημειώνονται με τριάδες x; y, z όπου x είναι το σύμβολο που διαβάζεται στην ταινία, y είναι αυτό που γράφεται και z είναι η κίνηση που εκτελεί η κεφαλή (L ή R).



Βρείτε ποιες συμβολοσειρές από 0 και 1 κάνουν τη μηχανή Turing να τερματίζει στην κατάσταση h. Ποια από τις παρακάτω σμβολοσειρές έχει αυτή την ιδιότητα;

Στη μηχανή Turing του σχήματος αρχική κατάσταση είναι η q και τελική κατάσταση είναι η h. Τα σύμβολα της ταινίας είναι τα 0, 1 και □, όπου □ είναι το σύμβολο του κενού. Το R σημαίνει ότι η κεφαλή εκτελεί κίνηση προς τα δεξιά και το L προς τα αριστερά. Οι μεταβάσεις σημειώνονται με τριάδες x; y, z όπου x είναι το σύμβολο που διαβάζεται στην ταινία, y είναι αυτό που γράφεται και z είναι η κίνηση που εκτελεί η κεφαλή (L ή R).



Εκτελέστε τον υπολογισμό της μηχανής Turing με είσοδο 1010110 και αναγνωρίστε ποια από τις παρακάτω συνολικές καταστάσεις εμφανίζεται σε αυτόν.

Στη μη ντεντερμινιστική μηχανή Turing του σχήματος αρχική κατάσταση είναι η q0 και τελική κατάσταση είναι η f. Τα σύμβολα της ταινίας είναι τα 0, 1 και □, όπου □ είναι το σύμβολο του κενού. Το R σημαίνει ότι η κεφαλή εκτελεί κίνηση προς τα δεξιά και το L προς τα αριστερά. Οι μεταβάσεις σημειώνονται με τριάδες x; y, z όπου x είναι το σύμβολο που διαβάζεται στην ταινία, y είναι αυτό που γράφεται και z είναι η κίνηση που εκτελεί η κεφαλή (L ή R).



Εκτελέστε όλους τους υπολογισμούς μήκους 5 από τη συνολική κατάσταση (q0, 1010) και αναγνωρίστε ποια από τις παρακάτω συνολικές καταστάσεις προσεγγίζεται σε ακριβώς 5 βήματα.

Στη μηχανή Turing του σχήματος αρχική κατάσταση είναι η q0 και τελική κατάσταση είναι η f. Τα σύμβολα της ταινίας είναι τα 0, 1 και □, όπου □ είναι το σύμβολο του κενού. Το R σημαίνει ότι η κεφαλή εκτελεί κίνηση προς τα δεξιά και το L προς τα αριστερά. Οι μεταβάσεις σημειώνονται με τριάδες x; y, z όπου x είναι το σύμβολο που διαβάζεται στην ταινία, y είναι αυτό που γράφεται και z είναι η κίνηση που εκτελεί η κεφαλή (L ή R).



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