Υπολογισιμότητα, Λογική θεμελίωση πληροφορικής, Ιστορική αναδρομή στο πρόβλημα αποκρισιμότητας μαθηματικών προτάσεων, Eπιλυσιμότητα ή υπολογισιμότητα προβλημάτων με μηχανιστικό, δηλαδή αλγοριθμικό, τρόπο. Απλά ισοδύναμα υπολογιστικά μοντέλα: μηχανές Turing, προγράμματα WHILE. Επαγωγή και αναδρομή, κωδικοποίηση και σημασιολογία. Θεωρία σταθερού σημείου. Θεωρία Tarski και υπολογιστικών στρατηγικών. Αριθμητική ιεραρχία. Προχωρημένα θέματα από την θεωρία τυπικών. Γραμματικών. Υπολογιστική Πολυπλοκότητα. Σχέσεις μεταξύ κλάσεων πολυπλοκότητας (L --> NL --> P --> NP \--> PSPACE = NPSPACE --> EXPTIME). Co-κλάσεις, Αναγωγές και Πληρότητα. Μαντεία. Πολυωνυμική ιεραρχία. Πιθανοτικές, τυχαιότητα (randomness). Διαλογικές/αλληλεπίδραση, PCP. Μετρητικές κλάσεις. Προσεγγιστική Πολυπλοκότητα. Πολυπλοκότητα αναζήτησης. Παραμετρική πολυπλοκότητα. Κβαντική πολυπλοκότητα.