Wykład monograficzny z ćwiczeniami (30+30 godzin) prowadzony przez prof. Marcina Mostowskiego. Odbywa się w czwartki od 13:00 do 16:30 w II semestrze roku akademickiego 2006/2007.
Plan wykładu
1. Intuicyjne pojęcie obliczalności i jego matematyczne modele.
2. Rachunki logiczne jako pierwowzór modeli obliczeń.
3. Podstawowe modele obliczeń (maszyny rejestrowe RAM, maszyny Turinga, funkcje rekurencyjne) i ich wzajemna równoważność.
4. Teza Churcha i jej empiryczne uzasadnienia.
5. Klasyfikacja zbiorów obliczalnych (elementarna rekurencyjność, pierwotna rekurencyjność).
6. Rekurencyjna przeliczalność.
7. Rekurencyjność w granicy (algorytmiczna teoria uczenia się).
8. Hierarchia arytmetyczna, przykład zastosowania twierdzenia Tarskiego o niedefiniowalności prawdy.
9. Stopnie nierozstrzygalności.
10. Praktyczna obliczalność, Teza Edmondsa.
11. Klasy złożoności obliczeniowej (PTIME, NPTIME, EXPTIME, LOGSPACE, NLOGSPACE, PSPACE).
12. Teoria modeli skończonych (Twierdzenie Fagina).
13. Reprezentowalność w modelach skończonych.
14. Definicje prawdy w modelach skończonych.
15. Teza Churcha, próba uzasadnienia.
Dla kogo?
Dla studentów filozofii o zacięciu logicznym, po kursie Logiki II (lub posiadających doświadczenia w kontaktach z matematyką, informatyką bądź logiką).
Sposoby zaliczania
Wykład kończy się egzaminem. Niewykluczone kolokwium w połowie semestru.
WAŻNE: Wstęp do teorii obliczeń jest traktowany jako roczny wykład monograficzny.