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

Πληροφορίες

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



  • Τετάρτη 15:00-17:00 στην Γ41, τμ. Μαθηματικών ΕΚΠΑ
  • Παρασκευή 9:00-11:00 στην Γ41, τμ. Μαθηματικών ΕΚΠΑ

 

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



1. Σχέσεις, Συναρτήσεις, Γλώσσες, Προβλήματα, Επαγωγή, Αποδεικτικές τεχνικές.

2. Μηχανές Turing,  
    Παραδείγματα Μηχανών Turing,
    Turing Αποφάνσιμες γλώσσες,
    Σχέσεις κλειστότητας για Turing Αποφάνσιμες  Γλώσσες,
    Turing Αναγνωρίσιμες  Γλώσσες,
    Σχέσεις κλειστότητας για Turing Αναγνωρίσιμες  Γλώσσες.

3. Turing Απαριθμήσιμες Γλώσσες,
    Ισοδυναμία Turing Αναγνωρίσιμων  Γλωσσών και Turing Απαριθμήσιμων Γλωσσών,
    (Turing) Υπολογίσιμες συναρτήσεις,
    Παραδείγματα Υπολογίσιμων Συναρτήσεων.

4. Παραλλαγές/Επεκτάσεις Μηχανών Turing,
    Μη-Ντετερμινιστικές Μηχανές Turing,
    Θεώρημα Ισοδυναμίας Μηχανών Turing και Μη-Ντετερμινιστικών Μηχανών Turing,
    Η Θέση Turing–Church, η έννοια του Αλγορίθμου.

5. Γενικές γραμματικές,
    Γλώσσες που γεννιούνται από γενικές γραμματικές και
    η  ισοδυναμία τους με τις Turing Αναγνωρίσιμες  Γλώσσες.

6. Πρωτογενώς Αναδρομικές Συναρτήσεις,
    μ-αναδρομικές συναρτήσεις,
    Ισοδυναμία μ-αναδρομικών συναρτήσεων με τις (Turing) Υπολογίσιμες συναρτήσεις.

7. Καθολικές Μηχανές Turing,
    Το πρόβλημα του τερματισμού και η μη αποφανσιμότητά του,
    Διαγωνιοποίηση,
    Αναγωγές,
    Παραδείγματα Μη-αποφάνσιμων και Μη-αναγνωρίσιμων γλωσσών,
    Επιπλέον Παραδείγματα Μη-αναγνωρίσιμων και Μη-αναγνωρίσιμων γλωσσών,
    Το θεώρημα του Rice,
    (Το πρόβλημα της αντιστοιχίας του Post).

8. Αυτοαναφορά,
    Το Θεώρημα της Αναδρομής, 
    Εφαρμογές του Θεωρήματος Αναδρομής,
    Αποφανσιμότητα λογικών θεωριών,
    Αναγωγές κατά Turing.

9. Βαθμοί μη-αποφανσιμότητας,
    Προφητείες,
    Το θεώρημα της αριθμητικής ιεραρχίας (ιεραρχία Kleene),
    Ταξινόμηση προβλημάτων στην αριθμητική ιεραρχία.

Βοηθήματα



- 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