Modele i obliczenia 3800-MO24-S
Seminarium „Modele i obliczenia” jest kontynuacją zajęć odbywających się pod tą samą nazwą w latach poprzednich. Zajęcia w roku 2024/2025 są skierowane i do dotychczasowych uczestników seminarium, i do nowych chętnych osób zainteresowanych logiką.
Poniżej są wymienione proponowane tematy do omówienia na seminarium. Wykaz ten może ulec modyfikacji w oparciu o sugestie ze strony uczestników seminarium.
Uczestnicy są zachęcani do proponowania własnych tematów referatów, o ile tematy te dotyczą szeroko rozumianej logiki albo teorii obliczeń. Dopuszczalne są referaty dotyczące zastosowania metod logiki i matematyki do analizy problemów interesujących z punktu widzenia filozofa, a także mniej formalne referaty omawiające zagadnienia z zakresu filozofii logiki, filozofii obliczeń oraz filozofii matematyki.
a) Zbiory rekurencyjne, rekurencyjnie przeliczalne, algorytmicznie wyuczalne. Stopnie Turinga.
b) Różne konstrukcje przekątniowe oraz priorytetowe w teorii obliczeń.
c) Pojęcie struktury obliczalnej. Relacje wewnętrznie obliczalne oraz relatywnie wewnętrznie obliczalne.
d) Spektra stopni struktur.
e) Struktury obliczalnie kategoryczne oraz obliczalnie stabilne.
f) Hierarchia skoków Turinga.
g) Elementy wiedzy o logikach infinitarnych.
h) Funkcje pierwotnie rekurencyjne. Wstęp do teorii struktur punktualnych.
Rodzaj przedmiotu
Założenia (opisowo)
Koordynatorzy przedmiotu
Efekty kształcenia
Nabyta wiedza:
- Zna podstawowe pojęcia z zakresu teorii obliczeń oraz teorii struktur obliczalnych.
- Zna podstawowe twierdzenia opisujące własności tych pojęć.
Nabyte umiejętności:
- Potrafi zrozumieć różne dowody przeprowadzone metodą przekątniową oraz metodą priorytetu.
- Potrafi zaklasyfikować wiele relacji oraz struktur ze względu na ich własności obliczeniowe.
- Potrafi skonstruować formuły infinitarne definiujące relacje oraz struktury.
Nabyte kompetencje społeczne:
- Umie przedstawiać swoje argumenty (formalne oraz filozoficzne).
- Umie analizować argumenty prezentowane przez innych i odnosić się do nich w sposób merytoryczny.
Kryteria oceniania
Aktywność na zajęciach, w każdym semestrze wygłoszenie na zajęciach referatu albo napisanie pracy zaliczeniowej na uzgodniony z prowadzącym temat.
Dopuszczalna liczba nieobecności podlegających usprawiedliwieniu: 2 w semestrze
Literatura
Ash C. J., Knight H., Computable Structures and the Hyperarithmetical Hierarchy.
Bazhenov N., Downey R., Kalimullin I., Melnikov A., Foundations of online structure theory. The Bulletin of Symbolic Logic (2019).
Enderton H., A Mathematical Introduction to Logic.
Hopcroft J.H., Ullman J.D., Introduction to Automata Theory, Languages and Computation.
Lempp S., Priority Arguments in Computability Theory, Model Theory, And Complexity Theory (skrypt dostępny online).
Montalbán A., Computable Structure Theory: Within the Arithmetic.
Montalbán A., Computable Structure Theory: Beyond the Arithmetic.
Rogers H., Theory of Recursive Functions and Effective Computability.
Shore R.A., Computable Structures: Presentations Matter (skrypt dostępny online).
Sipser M., Introduction to the Theory of Computation.
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: