Μηχανή Turing

Mathletic · #1

Γειά σας!!

Βλέπω μια λυμένη άσκηση σχετικά με μηχανές Turing.

Δώστε μια μηχανή Turing, η οποία μεταφράζει την είσοδο $x\in \{0,1\}^\star$ ως δυαδικό αριθμό και υπολογίζει την συνάρτηση f(x)=2x-4

. Το πεδίο ορισμού της

είναι $\mathbb{N}-\{0,1\}$ .

Η λύση είναι η εξής:
Για $a\in \{0,1\}$

: turing.PNG (10.3 KiB) Προβλήθηκε 2046 φορές

Μπορείτε να μου εξηγήσετε την λειτουργία αυτής της μηχανής?

dement · #2

Πολύ συνοπτικά:

1. Στην z_0

μετακινούμαστε στο ψηφίο των μονάδων, βάζουμε δεξιά ένα μηδενικό (πολλαπλασιάζουμε επί

) και μπαίνουμε στην z_1

.

2. Στην z_1

μετακινούμαστε αριστερά στο ψηφίο των τετράδων (πρώην δυάδων) και μπαίνουμε στην z_2

. Αν ο αριθμός τελειώσει πριν φτάσουμε, σφάλμα.

3. Στην z_2

αφαιρούμε

, μετακινούμενοι αριστερά και μετατρέποντας τα

σε

(τα κρατούμενα) μέχρι να βρούμε ψηφίο

, οπότε το μηδενίζουμε, ολοκληρώνεται η αφαίρεση και μπαίνουμε στην z_3

. Αν ο αριθμός τελειώσει πριν τελειώσει η αφαίρεση, σφάλμα.

4. Στην z_3

μετακινούμαστε στο ψηφίο τέρμα αριστερά και επιτυχές τέλος.

Mathletic · #3

Για να δω αν το κατάλαβα, προσπάθησα να κάνω την εξής άσκηση:
Δώστε μια μηχανή Turing, η οποία για είσοδο $x=x_1x_2\dots x_n$ υπολογίζει την έξοδο

, όπου $b=(x_1+x_2+\dots +x_n)\pmod 2$ .

Η ιδέα μου είναι η εξής:
Στην z_0

διαβάζουμε άρτιο πλήθος μονάδων και στην z_1

περιττό πλήθος μονάδων. Στην z_2

φτάνουμε στο τελευταίο ψηφίο και αναλόγως επιστρέφουμε το αποτέλεσμα

ή

.

Είναι σωστό αυτό?

Η συνάρτηση μετάβασης της μηχανής αυτής είναι η εξής?

$\\ (z_0,0) \mapsto (z_0, 0, R) \\ (z_0, 1)\mapsto (z_1, 1, R) \\ (z_0, \square ) \mapsto (z_2, 0, R)$

$\\ (z_1,0) \mapsto (z_1, 0, R) \\ (z_1, 1)\mapsto (z_0, 1, R) \\ (z_1, \square ) \mapsto (z_2, 1, R)$

$\\ (z_2,0) \mapsto (\square, 0, R) \\ (z_2, 1)\mapsto (\square, 1, R)$

Είναι σωστό αυτό που έχω κάνει?

dement · #4

Μου φαίνεται εντάξει. Προσπάθησε να χρησιμοποιείς το ελληνικό ερωτηματικό (;).

Mathletic · #5

Ωραία!

Προσπάθησα επίσης μια άλλη άσκηση που ζητάει μια μη-αιτιοκρατική μηχανή Turing με 2 ταινίες, η οποία αποδέχεται την γλώσσα

επί του $\Sigma=\{0,1\}$ σε

βήματα, με είσοδο μήκους

, $L=\{x1y \mid |y|=2|x|>0\}$ .

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

Mathletic · #6

Μήπως θα μπορούσαμε κάνομε το εξής;
Να αντιγράψουμε στην δεύτερη ταινία την είσοδο της πρώτης ταινίας, η κεφαλή της πρώτης ταινίας ξεκινάει από τα αριστερά και σε κάθε βήμα μετακινείται κατά 1 προς τα δεξιά και η κεφαλή της δεύτερης ταινίας ξεκινάει από τα δεξιά και σε κάθε βήμα μετακινείται κατά 2 προς τα αριστερά. Αν ισχύει x1y

και

τότε στο τέλος θα ελέγξουμε αν το 1 βρίσκεται ανάμεσα στα x και y.

Μηχανή Turing

Μηχανή Turing

Re: Μηχανή Turing

Re: Μηχανή Turing

Re: Μηχανή Turing

Re: Μηχανή Turing

Re: Μηχανή Turing

Μέλη σε σύνδεση