Modele i obliczenia 3800-MO23-S
Seminarium „Modele i obliczenia” jest kontynuacją zajęć odbywających się pod tą samą nazwą w roku poprzednim. Zajęcia w roku 2023/2024 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) Porównywanie trudności obliczeniowej problemów. Różne rodzaje redukowalności. Stopnie Turinga i podstawowe wiadomości o ich strukturze. Twierdzenie Friedberga-Muchnika.
b) Elementy wiedzy o liczbach porządkowych (wykraczającej poza materiał omówiony na Logice II).
c) Problem adekwatności ujęcia strukturalistycznego w filozofii matematyki.
d) Funkcje rekurencyjne i pierwotnie rekurencyjne. Filozoficzne konsekwencje tego rozróżnienia.
e) Wstęp do teorii struktur obliczalnych oraz teorii struktur punktualnych (punctual structures).
f) Elementy wiedzy o logikach infinitarnych oraz ewentualnie innych niestandardowych logikach.
g) Pojęcie algorytmicznej wyuczalności.
h) Nieskończoność potencjalna i aktualna. Koncepcja FM-dziedzin Marcina Mostowskiego.
Rodzaj przedmiotu
Założenia (opisowo)
Koordynatorzy przedmiotu
Efekty kształcenia
Nabyta wiedza:
- Zna różne rodzaje redukowalności zbiorów i ich własności.
- Zna własności liczb porządkowych.
- Zna pojęcie obliczalnej liczby porządkowej
- Zna pojęcie postaci normalnej Cantora.
- Zna definicję funkcji rekurencyjnej (częściowej oraz całkowitej) oraz pierwotnie rekurencyjnej.
- Zna podstawowe pojęcia i twierdzenia dotyczące struktur obliczalnych.
- Zna definicję struktury punktualnej.
- Posiada podstawową wiedzę na temat logik infinitarnych.
- Zna pojęcie algorytmicznej wyuczalności według Golda i Putnama.
- Rozumie różnicę między nieskończonością potencjalną a aktualną.
- Zna pojęcie FM-dziedziny według Marcina Mostowskiego.
Nabyte umiejętności:
- Potrafi sformułować twierdzenie Friedberga-Muchnika oraz rozumie jego dowód.
- Potrafi wskazać argumenty wspierające oraz podważające stosowalność stanowiska strukturalistycznego wobec teorii obliczeń.
- Potrafi wskazać funkcje rekurencyjne, które nie są całkowite oraz które nie są pierwotnie rekurencyjne.
- Potrafi opisać filozoficzne konsekwencje rozróżnienie na funkcje rekurencyjne i pierwotnie rekurencyjne.
- Potrafi wyjaśnić różnice między strukturami obliczalnymi a punktualnymi (od strony formalnej i filozoficznej).
- Potrafi wyjaśnić różnicę między obliczalnością a algorytmiczną wyuczalnością.
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, 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
Lista będzie konsultowana na bieżąco z uczestnikami seminarium i może ulec zmianie.
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.
Gold E.M., Limiting Recursion, The Journal of Symbolic Logic (1965).
Gold E.M., Language Identification in the Limit, Information and Control (1967).
Halbach V., Horsten L., Computational Structuralism, w: Philosophia Mathematica 13(2): 174-186 (2005).
Hopcroft J.H., Ullman J.D., Introduction to Automata Theory, Languages and Computation.
Kaye M., Models of Peano Arithmetic.
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.
Mostowski M., Potential Infinity and the Church Thesis, Fundamenta Informaticae (2008).
Mostowski M. Zdanowski K., FM-Representability and Beyond, Lecture Notes in Computer Science (2005).
Putnam H., Trial and Error Predicates and the Solution to a Problem of Mostowski, The Journal of Symbolic Logic (1965).
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: