Περιγραφή μαθήματος

Κωδικός μαθήματος: ΜΥΕ022

Εβδομαδιαίες ώρες διδασκαλίας: 3,2,0

Εξάμηνο σπουδών: >=6ο

Διδακτικές Μονάδες: 4

Μονάδες ECTS: 5

Ιστοσελίδα Μαθήματος:

Προσφερόμενο:

Προαπαιτούμενα:

Περιεχόμενο:

Πρωταρχικές αναδρομικές συναρτήσεις και ένα ισοδύναμο υπολογιστικό μοντέλο. Μερικές αναδρομικές συναρτήσεις και ισοδύναμα υπολογιστικά μοντέλα. Η Θέση του Church. Κανονική μορφή Kleene. Το Θεώρημα των παραμέτρων. Μη επιλυσιμότητα. Αναγωγές και πληρότητα. Αναδρομικά και αναδρομικά αριθμήσιμα σύνολα. Η αριθμητική ιεραρχία. Γραμματικές και η Ιεραρχία Chomsky. Ιδιότητες κλειστότητας. Επιλύσιμα και μη επιλύσιμα προβλήματα σε γραμματικές.

Παρατηρήσεις: