Μάθημα : Αναδρομικές Συναρτήσεις

Καλησπέρα σε όλα,

Ακολουθεί η ύλη του μαθήματος, με αναφορές από το βιβλίο του Sipser και τις σημειώσεις του κ. Ζώρου. Φυσικά οποιαδήποτε άλλη πηγή θέλει να χρησιμοποιήσει κάποιο που καλύπτει τα παρακάτω θέματα στο βάθος που το κάναμε και στο μάθημα, είναι απολύτως οκ να το κάνει.

Ειδικά για όσο κόσμο διαβάζει από Sipser, οτιδήποτε αναφέρεται στο πρώτο μέρος του βιβλίου (Κανονικές γλώσσες, ασυμφραστικές γραμματικές, αυτόματα) είναι τυπικά εκτός ύλης. Μπορεί φυσικά να βοηθήσει στην κατανόηση, αν κάποιο θέλει να αφιερώσει τον χρόνο/κόπο.

1) Μηχανές Turing: Sipser παρ. 3.1, Ζώρος Κεφ.1 (όχι παρ. 1.3)

2) Κλάσεις REC, RE, coRE: Sipser παρ. 4.2, Ζώρος Κεφ.5

3) Αναγωγές: Sipser Κεφ.5 (όχι παρ. 5.1.1, 5.2), Ζώρος παρ. 5.2.2

4) Θεώρημα Rice: Ζώρος παρ. 6.1

5) Θεώρημα Αναδρομής: Sipser παρ. 6.1, Ζώρος Κεφ.7 (όχι παρ. 7.3)

6) Αναγωγές κατά Turing: Sipser παρ. 6.3 , Ζώρος παρ. 8.1

Γ. Λ.