Μηχανή Turing
Μηχανή Turing
Γειά σας!!
Βλέπω μια λυμένη άσκηση σχετικά με μηχανές Turing.
Δώστε μια μηχανή Turing, η οποία μεταφράζει την είσοδο ως δυαδικό αριθμό και υπολογίζει την συνάρτηση . Το πεδίο ορισμού της είναι .
Η λύση είναι η εξής:
Για
Μπορείτε να μου εξηγήσετε την λειτουργία αυτής της μηχανής?
Βλέπω μια λυμένη άσκηση σχετικά με μηχανές Turing.
Δώστε μια μηχανή Turing, η οποία μεταφράζει την είσοδο ως δυαδικό αριθμό και υπολογίζει την συνάρτηση . Το πεδίο ορισμού της είναι .
Η λύση είναι η εξής:
Για
Μπορείτε να μου εξηγήσετε την λειτουργία αυτής της μηχανής?
Re: Μηχανή Turing
Πολύ συνοπτικά:
1. Στην μετακινούμαστε στο ψηφίο των μονάδων, βάζουμε δεξιά ένα μηδενικό (πολλαπλασιάζουμε επί ) και μπαίνουμε στην .
2. Στην μετακινούμαστε αριστερά στο ψηφίο των τετράδων (πρώην δυάδων) και μπαίνουμε στην . Αν ο αριθμός τελειώσει πριν φτάσουμε, σφάλμα.
3. Στην αφαιρούμε , μετακινούμενοι αριστερά και μετατρέποντας τα σε (τα κρατούμενα) μέχρι να βρούμε ψηφίο , οπότε το μηδενίζουμε, ολοκληρώνεται η αφαίρεση και μπαίνουμε στην . Αν ο αριθμός τελειώσει πριν τελειώσει η αφαίρεση, σφάλμα.
4. Στην μετακινούμαστε στο ψηφίο τέρμα αριστερά και επιτυχές τέλος.
1. Στην μετακινούμαστε στο ψηφίο των μονάδων, βάζουμε δεξιά ένα μηδενικό (πολλαπλασιάζουμε επί ) και μπαίνουμε στην .
2. Στην μετακινούμαστε αριστερά στο ψηφίο των τετράδων (πρώην δυάδων) και μπαίνουμε στην . Αν ο αριθμός τελειώσει πριν φτάσουμε, σφάλμα.
3. Στην αφαιρούμε , μετακινούμενοι αριστερά και μετατρέποντας τα σε (τα κρατούμενα) μέχρι να βρούμε ψηφίο , οπότε το μηδενίζουμε, ολοκληρώνεται η αφαίρεση και μπαίνουμε στην . Αν ο αριθμός τελειώσει πριν τελειώσει η αφαίρεση, σφάλμα.
4. Στην μετακινούμαστε στο ψηφίο τέρμα αριστερά και επιτυχές τέλος.
Δημήτρης Σκουτέρης
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Re: Μηχανή Turing
Για να δω αν το κατάλαβα, προσπάθησα να κάνω την εξής άσκηση:
Δώστε μια μηχανή Turing, η οποία για είσοδο υπολογίζει την έξοδο , όπου .
Η ιδέα μου είναι η εξής:
Στην διαβάζουμε άρτιο πλήθος μονάδων και στην περιττό πλήθος μονάδων. Στην φτάνουμε στο τελευταίο ψηφίο και αναλόγως επιστρέφουμε το αποτέλεσμα ή .
Είναι σωστό αυτό?
Η συνάρτηση μετάβασης της μηχανής αυτής είναι η εξής?
Είναι σωστό αυτό που έχω κάνει?
Δώστε μια μηχανή Turing, η οποία για είσοδο υπολογίζει την έξοδο , όπου .
Η ιδέα μου είναι η εξής:
Στην διαβάζουμε άρτιο πλήθος μονάδων και στην περιττό πλήθος μονάδων. Στην φτάνουμε στο τελευταίο ψηφίο και αναλόγως επιστρέφουμε το αποτέλεσμα ή .
Είναι σωστό αυτό?
Η συνάρτηση μετάβασης της μηχανής αυτής είναι η εξής?
Είναι σωστό αυτό που έχω κάνει?
Re: Μηχανή Turing
Μου φαίνεται εντάξει. Προσπάθησε να χρησιμοποιείς το ελληνικό ερωτηματικό (;).
Δημήτρης Σκουτέρης
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Re: Μηχανή Turing
Ωραία!
Προσπάθησα επίσης μια άλλη άσκηση που ζητάει μια μη-αιτιοκρατική μηχανή Turing με 2 ταινίες, η οποία αποδέχεται την γλώσσα επί του σε βήματα, με είσοδο μήκους , .
Κάθε φορά που η μηχανή διαβάζει 1 θα πρέπει να ελέγχει αν το μήκος της υπολέξης πριν το 1 είναι το μισό του μήκους της υπολέξης μετά το 1, σωστά; Πώς ακριβώς μπορεί να γίνει αυτό με μια μη-αιτιοκρατική μηχανή Turing με 2 ταινίες; Μπορείτε να μου δώσετε μια ιδέα;
Προσπάθησα επίσης μια άλλη άσκηση που ζητάει μια μη-αιτιοκρατική μηχανή Turing με 2 ταινίες, η οποία αποδέχεται την γλώσσα επί του σε βήματα, με είσοδο μήκους , .
Κάθε φορά που η μηχανή διαβάζει 1 θα πρέπει να ελέγχει αν το μήκος της υπολέξης πριν το 1 είναι το μισό του μήκους της υπολέξης μετά το 1, σωστά; Πώς ακριβώς μπορεί να γίνει αυτό με μια μη-αιτιοκρατική μηχανή Turing με 2 ταινίες; Μπορείτε να μου δώσετε μια ιδέα;
Re: Μηχανή Turing
Μήπως θα μπορούσαμε κάνομε το εξής;
Να αντιγράψουμε στην δεύτερη ταινία την είσοδο της πρώτης ταινίας, η κεφαλή της πρώτης ταινίας ξεκινάει από τα αριστερά και σε κάθε βήμα μετακινείται κατά 1 προς τα δεξιά και η κεφαλή της δεύτερης ταινίας ξεκινάει από τα δεξιά και σε κάθε βήμα μετακινείται κατά 2 προς τα αριστερά. Αν ισχύει και τότε στο τέλος θα ελέγξουμε αν το 1 βρίσκεται ανάμεσα στα x και y.
Να αντιγράψουμε στην δεύτερη ταινία την είσοδο της πρώτης ταινίας, η κεφαλή της πρώτης ταινίας ξεκινάει από τα αριστερά και σε κάθε βήμα μετακινείται κατά 1 προς τα δεξιά και η κεφαλή της δεύτερης ταινίας ξεκινάει από τα δεξιά και σε κάθε βήμα μετακινείται κατά 2 προς τα αριστερά. Αν ισχύει και τότε στο τέλος θα ελέγξουμε αν το 1 βρίσκεται ανάμεσα στα x και y.
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες