Θεωρία Αναδρομής

Πληροφορίες

Πρόγραμμα διαλέξεων



Τρίτη και Τετάρτη 09:00-11:00 στην αίθουσα Α11 του τμ. Μαθηματικών του ΕΚΠΑ.

Περιεχόμενο Μαθήματος



0. ΕΙΣΑΓΩΓΗ
    Σχέσεις και συναρτήσεις, Λέξεις και γλώσσες
 
1. ΜΗΧΑΝΕΣ TURING
    Ορισμός Μηχανής Turing
    Τι κάνουν οι Μηχανές Turing;
    Επεκτάσεις Μηχανών Turing
    Κλειστότητα REC και RE ως προς συνολοθεωρητικές πράξεις

2. ΕΛΑΧΙΣΤΙΚΑ ΑΝΑΔΡΟΜΙΚΕΣ ΣΥΝΑΡΤΗΣΕΙΣ
    Πρωτογενώς αναδρομικές συναρτήσεις
    Φραγμένη ελαχιστοποίηση
    Πλήρης πρωτογενής αναδρομή
    Ελαχιστικά αναδρομικές συναρτήσεις
    Δεύτερος ορισμός υπολογίσιμων συναρτήσεων

3. ΓΕΝΙΚΕΣ ΓΡΑΜΜΑΤΙΚΕΣ-ΙΕΡΑΡΧΙΑ CHOMSKY
    Γενικές γραμματικές
    Γραμματικές με συμφραζόμενα
    Γραμματικές χωρίς συμφραζόμενα
    Κανονικές γραμματικές
    Ιεραρχία Chomsky

4. ΜΗ-ΑΠΟΦΑΝΣΙΜΟΤΗΤΑ
    Θέση Church-Turing
    Μη-αποφανσιμότητα γλωσσών

5. ΤΟ ΘΕΩΡΗΜΑ ΤΟΥ RICE
    Το Θεώρημα του Rice για αναδρομικές γλώσσες
    Το Θεώρημα του Rice για αναδρομικά απαριθμήσιμες γλώσσες

6. ΤΟ ΘΕΩΡΗΜΑ ΑΝΑΔΡΟΜΗΣ
    Μπορούν οι μηχανές να αυτο-αναπαράγονται;
    Το Θεώρημα Αναδρομής
    Το Πρώτο Θεώρημα Μη-πληρότητας του Gödel

7. ΑΡΙΘΜΗΤΙΚΗ ΙΕΡΑΡΧΙΑ
    Αριθμητική Ιεραρχία
    Αλγοριθμικές Αναγωγές
    Πληρότητας γλωσσών ως προς σχέση αναγωγής
    Πέρα από την Αριθμητική Ιεραρχία

Βοηθήματα



- 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