Να κατασκευάσετε μηχανή Turing

 Δίνεται η συνάρτηση

που ορίζεται ως

F(u)=uIu^R

(Α) Να κατασκευάσετε μηχανή Turing που την υπολογίζει. Θεωρούμε ότι αρχικά η
κεφαλή  είναι  στο  πρώτο  κενό  δεξιά  της  λέξης u και η μηχανή τερματίζει με την
κεφαλή στο I. Το αλφάβητο της μηχανής είναι το {a,b,I,#}.

(Β)  Να  κατασκευάσετε  Turing  μηχανή  που  υπολογίζει  τη  συνάρτηση

  Η  αρχική  θέση  της  κεφαλής  είναι  όπως  στο  (Α) και η
μηχανή τερματίζει με την κεφαλή στον πρώτο από τα αριστερά χαρακτήρα  της
εξόδου. Σας ζητείται να δώσετε δύο λύσεις:
1.  Μία στην οποία επιτρέπεται χρήση βοηθητικών συμβόλων και
2.  μία στην οποία δεν επιτρέπεται χρήση βοηθητικών συμβόλων.

(Γ) Να τρέξετε τη δεύτερη μηχανή με είσοδο τη συμβολοσειρά u = bbab. Μπορείτε
να υποθέσετε ότι η ταινία είναι άπειρη και προς τις δύο κατευθύνσεις.
ΠΑΡΑΤΗΡΗΣΗ: Για τη σύνταξη των μηχανών μπορείτε να χρησιμοποιήσετε τη Visual
Turing.