Υπολογιστική Πολυπλοκότητα — Μάιος 2023 — Θέμα 2 (χωρίς εκφώνηση)¶
Μεταγραφή της φωτογραφίας 2023-05-30_7.40.53_.png (λύση θέματος 2).
2023-05-30_7.40.53_.png¶
[Δεν υπάρχει μεταγραφή εκφώνησης: η φωτογραφία 2023-05-30_7.40.53_.png περιέχει μόνο απάντηση στο Θέμα 2 και δεν υπάρχει εκφώνηση του θέματος στον φάκελο.]
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: φωτογραφία λύσης θέματος 2 (η πηγή δεν αναγράφεται)
Προσοχή
Η πηγή της φωτογραφίας δεν αναγράφεται. Ο χαρακτηρισμός «community» βασίζεται στη μορφή της (λύση φοιτητή)· αν πρόκειται για κλειδί του διδάσκοντα, θα πρέπει να αλλάξει σε official.
Λύσεις — Υπολογιστική Πολυπλοκότητα — Μάιος 2023 (θέμα 2)¶
Λύση του θέματος 2. Η εκφώνηση δεν βρέθηκε στον φάκελο.
2023-05-30_7.40.53_.png¶
Θέμα 2 Απάντηση
α. Η μηχανή δεν είναι διαγνώστης διότι με είσοδο τη συμβολοσειρά 1 εγκλωβίζεται.
β. Η γλώσσα της μηχανής είναι: 1(01)^1(0∪1)^
[Σχήμα: διάγραμμα μηχανής Turing με καταστάσεις q_0, q_1, q_ΟΧΙ (τελική), q_ΝΑΙ (τελική). Αρχική κατάσταση: q_0. - q_0 → q_ΟΧΙ: 0→0,Α (ευθεία ακμή) και ⊔→0,Α (καμπύλη ακμή πάνω από την κατάσταση) - q_0 → q_1: 1→1,Δ - q_1 → q_0: 0→1,Δ - q_1 → q_ΝΑΙ: 1→0,Α - q_1 → q_1 (βρόχος): ⊔→0,Δ]