Θεωρία Αναδρομής (Μ.Π. Α.Λ.ΜΑ.)
Περίγραμμα
Μέθοδοι αξιολόγησης
Ως επιπλέον κίνητρο, οι φοιτητές θα κληθούν να επιλύσουν 4 πακέτα ασκήσεων που θα λειτουργούν βελτιωτικά στον συνολικό βαθμό που θα επιτύχουν στο μάθημα. Πιο συγκεκριμένα, οι φοιτητές θα κληθούν να σχηματίσουν ομάδες συνεργασίας (μέχρι 3 άτομα ανά ομάδα), οι ομάδες αυτές θα πρέπει να επιλύσουν τις ασκήσεις, να γράψουν τις απαντήσεις τους (κατά προτίμηση σε LaTeX) και να τις καταθέσουν στον διδάσκοντα μέσω της πλατφόρμας «η-τάξη».
Η επίλυση των πακέτων ασκήσεων είναι προαιρετική και δίνει τη δυνατότητα στους φοιτητές που θα ασχοληθούν με αυτές να βελτιώσουν τον τελικό βαθμό τους κατά το πολύ 2 μονάδες.
Ασκήσεις: Το πολύ 2 μονάδες (μισή μονάδα για κάθε πακέτο)
Εξέταση: 10 μονάδες
Τελικός βαθμός: min{βαθμός εξέτασης+βαθμός ασκήσεων, 10}
Περιεχόμενο Μαθήματος
Ορισμός Μηχανής Turing
Τι κάνουν οι Μηχανές Turing;
Επεκτάσεις Μηχανών Turing
2. ΕΛΑΧΙΣΤΙΚΑ ΑΝΑΔΡΟΜΙΚΕΣ ΣΥΝΑΡΤΗΣΕΙΣ
Πρωτογενώς αναδρομικές συναρτήσεις
Πλήρης πρωτογενής αναδρομή
Γενικές γραμματικές
Γραμματικές με συμφραζόμενα
Ιεραρχία Chomsky
5. ΜΗ-ΑΠΟΦΑΝΣΙΜΟΤΗΤΑ
Θέση Church-Turing
Μη-αποφανσιμότητα γλωσσών
6. ΤΟ ΘΕΩΡΗΜΑ ΤΟΥ RICE
Το Θεώρημα του Rice για αναδρομικές γλώσσες
Το Θεώρημα του Rice για αναδρομικά απαριθμήσιμες γλώσσες
7. ΤΟ ΘΕΩΡΗΜΑ ΑΝΑΔΡΟΜΗΣ
Μπορούν οι μηχανές να αυτο-αναπαράγονται;
Το Θεώρημα Αναδρομής
Το Πρώτο Θεώρημα Μη-πληρότητας του Gödel
8. ΑΡΙΘΜΗΤΙΚΗ ΙΕΡΑΡΧΙΑ
Αριθμητική Ιεραρχία
Αλγοριθμικές Αναγωγές
Πληρότητας γλωσσών ως προς σχέση αναγωγής
Πέρα από την Αριθμητική Ιεραρχία
Βοηθήματα
- Michael Sipser: Εισαγωγή στην Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης
- Harry R. Lewis, Χρήστος Παπαδημητρίου: Στοιχεία Θεωρίας Υπολογισμού, Εκδόσεις Κριτική
- John E. Hopcroft, Jefrey D. Ullman: Introduction to Automata Theory, Languages, and Computation (1st edition), Addison-Wesley
- Dexter C. Kozen: Automata and Computability, Springer
- Γιάννης Ν. Μοσχοβάκης: Αναδρομή και Υπολογισιμότητα
- Thomas Sudkamp: Languages and Machines An Introduction to the Theory of Computer Science (3rd Edition), Pearson