Προγραμματισμός < < Java Προγραμματισμός Πρόκληση: Δημιουργία απλής μηχανής Turing - dummies

Το 1936, ο μαθηματικός Alan Turing σχεδίασε ένα παραπλανητικά απλό τύπο υπολογιστικής μηχανής που ονομάζεται Turing Machine . Ο Τούρινγκ δεν έχτισε ποτέ μηχανή Turing. Αντ 'αυτού, ήταν μια υποθετική συσκευή που σχεδίαζε να βοηθήσει στη μελέτη της υπολογιστικής ικανότητας - δηλαδή, αν πολύπλοκα προβλήματα μπορούν να επιλυθούν με υπολογιστικά βήματα και αν μπορεί να επινοηθεί μια μηχανή που να μπορεί να λύσει οποιοδήποτε αξιόπιστο πρόβλημα. (Εάν ενδιαφέρεστε να μάθετε περισσότερα για την ιστορία ή την εφαρμογή των μηχανών Turing, μπορείτε να βρείτε πολλά άρθρα σχετικά με αυτά στο Διαδίκτυο. Απλά χρησιμοποιήστε οποιονδήποτε πάροχο αναζήτησης για να αναζητήσετε τη μηχανή Turing.)

Η λειτουργία μιας μηχανής Turing είναι απλή. Περιέχει μόνο μερικές βασικές έννοιες:

1. Η καρδιά μιας μηχανής Turing είναι μια απείρως μεγάλη ταινία που χωρίζεται σε κελιά πάνω στα οποία μπορούν να γραφτούν πληροφορίες.

   Στην πράξη, φυσικά, καμία φυσική συσκευή δεν μπορεί να έχει άπειρο αριθμό κυττάρων. Αλλά στη θεωρία μιας μηχανής Turing, η ταινία είναι άπειρη.

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

   Η μηχανή Turing περιέχει μια κεφαλίδα ανάγνωσης και εγγραφής

3. που βρίσκεται πάντα πάνω από ένα (και μόνο) από τα κελιά της ταινίας.

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

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

4. , το οποίο αντιπροσωπεύεται από ένα σύμβολο όπως ένα γράμμα του αλφαβήτου.

5. Όπως κάθε υπολογιστή, μπορεί να προγραμματιστεί μια μηχανή Turing. Ωστόσο, ένα πρόγραμμα για μια μηχανή Turing δεν θυμίζει από μακριά ένα πρόγραμμα Java. Αντ 'αυτού, ένα πρόγραμμα Turing Machine είναι απλά ένα σύνολο κανόνων που αξιολογούνται για να καθορίσουν ποιες ενέργειες θα πρέπει να λάβει η μηχανή. Κάθε κανόνας προσδιορίζει μια ενέργεια που πρέπει να ληφθεί όταν το τρέχον κελί περιέχει ένα δεδομένο σύμβολο και το μηχάνημα βρίσκεται σε δεδομένη κατάσταση.Για παράδειγμα, ένας κανόνας μπορεί να υπαγορεύει τι πρέπει να κάνει εάν το τρέχον κελί περιέχει 1 και η κατάσταση του μηχανήματος είναι "a". Κάθε κανόνας μπορεί να καθορίσει οποιαδήποτε από τις τρεις ενέργειες:

Διαγράψτε το τρέχον κελί ή γράψτε μια νέα τιμή στο κελί.

Μετακινήστε την ταινία ένα κύτταρο προς τα αριστερά ή ένα κελί προς τα δεξιά.

Αλλάξτε την κατάσταση του μηχανήματος σε νέα κατάσταση.

• Για παράδειγμα, ένας κανόνας μπορεί να καθορίζει ότι αν το τρέχον κελί περιέχει 1 και η κατάσταση του μηχανήματος είναι "a", η μηχανή Turing πρέπει να γράψει ένα 0 στο τρέχον κελί, να προωθήσει την ταινία ένα κελί προς τα δεξιά και να αλλάξει η κατάσταση του μηχανήματος σε "b. "

• Εκτός από ένα πρόγραμμα, η ταινία του Turing Machine μπορεί να έχει μια αρχική τιμή.

• Αυτό είναι; αυτός είναι ο ολόκληρος ορισμός μιας μηχανής Turing. Παρά την απλότητα του, μια μηχανή Turing μπορεί να υπολογίσει οτιδήποτε από 2 + 2 στην τροχιά ενός πυραύλου προς τον Άρη.

Για αυτή την πρόκληση, πρέπει να δημιουργήσετε μια πολύ απλή μηχανή Turing. Για να απλοποιήσετε το πρόβλημα, αποδεχτείτε τους ακόλουθους περιορισμούς σε αυτή την έκδοση του μηχανήματος Turing:

Η ταινία δεν χρειάζεται να είναι άπειρη.

Μπορείτε να χρησιμοποιήσετε οποιαδήποτε λειτουργία Java - έναν πίνακα, μια συμβολοσειρά ή μια συλλογή - για να αναπαριστάτε την κασέτα.

(Σημειώστε ότι παρόλο που η ταινία δεν χρειάζεται να είναι άπειρη, πρέπει να μπορείτε εύκολα να μετακινηθείτε αριστερά ή δεξιά από την τρέχουσα κελιά. Εάν επιλέξετε να χρησιμοποιήσετε έναν πίνακα, μην ξεκινήσετε με το τρέχον κελί στο στοιχείο 0 επειδή δεν θα μπορείτε να μετακινηθείτε αριστερά από εκεί.)

• Ένα κελί μπορεί να είναι άδειο ή μπορεί να περιέχει οποιοδήποτε γράμμα ή αριθμό. Ένα κενό κελί αντιπροσωπεύεται από ένα χαρακτήρα υπογράμμισης.

  Η κατάσταση μπορεί να είναι κάθε άλλος αλφαριθμητικός χαρακτήρας.

• Το πρόγραμμα για το Turing Machine θα διαβαστεί από ένα αρχείο κειμένου. Αυτό το αρχείο κειμένου περιέχει έναν κανόνα ανά γραμμή. Κάθε κανόνας περιέχει πέντε χαρακτήρες, χωρισμένους με κενά, που παρέχουν τις λεπτομέρειες για κάθε κανόνα ως εξής:

• Τρέχουσα κελιά:

• Η τιμή που πρέπει να αντιστοιχιστεί για το τρέχον κελί. Τρέχουσα κατάσταση:

  • Η τιμή που πρέπει να αντιστοιχιστεί για την τρέχουσα κατάσταση του μηχανήματος. Νέο κελί:

  • Η τιμή για εγγραφή στο νέο κελί. _ για να διαγράψετε το κελί, * για να αφήσετε το κελί αμετάβλητο. Κίνηση:

  • L ή R για να μετακινήσετε την ταινία αριστερά ή δεξιά. H για να σταματήσει το πρόγραμμα. οποιοδήποτε άλλο χαρακτήρα για να μην μετακινήσετε την ταινία. Νέα κατάσταση:

  • Η νέα τιμή για την κατάσταση του μηχανήματος. Για παράδειγμα, το παρακάτω λέει ότι όταν το τρέχον κελί είναι 1 και η κατάσταση είναι "a", το τρέχον κελί θα πρέπει να ρυθμιστεί σε 0, η ταινία μετακινήθηκε ένα κύτταρο προς τα αριστερά και η κατάσταση θα πρέπει να ρυθμιστεί σε " b: "

  • 1 a 0 L b Η πρώτη γραμμή του αρχείου κειμένου θα πρέπει να περιέχει μια συμβολοσειρά που να αντιπροσωπεύει τις αρχικές τιμές της ταινίας.

• Η δεύτερη γραμμή του αρχείου κειμένου πρέπει να περιέχει την αρχική κατάσταση.

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

  • Μια πιθανή διεπαφή Turing Machine.

  • Ακολουθούν μερικές σκέψεις για τη δημιουργία της διεπαφής:

Τιμή και τρέχον κελί:

Τουλάχιστον, θα πρέπει να εμφανίσετε την τιμή της ταινίας και να επισημάνετε το τρέχον κελί.

Εργαλεία και οθόνη:

• Θα πρέπει επίσης να παρέχετε τη δυνατότητα εκκίνησης, διακοπής ή επανεκκίνησης της εκτέλεσης του προγράμματος και θα πρέπει να εμφανίσετε τα αποτελέσματα κάθε βήματος του προγράμματος. Εκτέλεση προγράμματος:

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

• : Θα πρέπει να δώσετε κουμπιά που επιτρέπουν στο χρήστη να φορτώσει ένα πρόγραμμα Turing Machine από ένα αρχείο κειμένου και να αφήσει τον χρήστη να επαναφέρει το μηχάνημα για να εκτελέσει ξανά το πρόγραμμα. Ακολουθεί μια συμβουλή για την υλοποίηση της άπειρης κασέτας: Χρησιμοποιήστε τρεις μεταβλητές συμβολοσειράς για να συγκρατήσετε τις τιμές της ταινίας, μία για τον μοναδικό χαρακτήρα που είναι αποθηκευμένο στο τρέχον κελί, ένα δεύτερο για τους χαρακτήρες αριστερά του τρέχοντος κελιού και ένα τρίτο για τους χαρακτήρες στα δεξιά του τρέχοντος κελιού. Στη συνέχεια, μπορείτε να μετακινήσετε εύκολα την τρέχουσα κελιά αριστερά ή δεξιά, χρησιμοποιώντας τον σωστό συνδυασμό των λειτουργιών συνένωσης και υποσέλιδου.

• Μπορείτε να βρείτε τη λύση αυτής της πρόκλησης στην καρτέλα Downloads (Λήψεις) της σελίδας προϊόντος Java All-in-One For Dummies,

4η έκδοση.

Καλή τύχη!