Μάθημα : Θεωρία Αναδρομής 2018-2019

Η ύλη του μαθήματος θα καλύψει κομμάτια από τα παρακάτω βιβλία

 

Michael Sipser: Εισαγωγή στην Θεωρία Υπολογισμού 
Lewis και Παπαδημητρίου: Στοιχεία Θεωρίας Υπολογισμού
Hopcroft and Ullman: Introduction to Automata Theory, Languages, and Computation (1η έκδοση)
Dexter Kozen: Automata and Computability
Γιάννης Ν. Μοσχοβάκης: Αναδρομή και Υπολογισιμότητα

 

 

 

 

Η ύλη του μαθήματος είναι η εξής:

 

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),
Ταξινόμηση προβλημάτων στην αριθμητική ιεραρχία.