Struktury, obliczenia, wyuczalność 3800-SOW26-S

Planowane referaty na seminarium dotyczą przede wszystkim wymienionych poniżej zagadnień.
Studenci mogą jednak zgłaszać własne tematy wystąpień, dotyczące szeroko rozumianej logiki i teorii
obliczeń.
Dopuszczalne są również referaty dotyczące filozoficznych zastosowań metod logiki i matematyki, a
także mniej formalne referaty omawiające zagadnienia z zakresu filozofii logiki, filozofii obliczeń
oraz filozofii matematyki.
a) Pojęcia z zakresu teorii obliczeń i ich własności: obliczalność, rekurencyjna przeliczalność,
algorytmiczna wyuczalność, obliczenia z wyrocznią, stopnie Turinga.
b) Elementy teorii struktur obliczalnych i punktualnych.
c) Konstrukcje przekątniowe oraz priorytetowe w teorii obliczeń.
d) Uczenie się struktur w stylu Golda.
e) Obliczalność generyczna (generic) i zgrubna (coarse).

Koordynatorzy przedmiotu

Michał Wrocławski

Rodzaj przedmiotu

seminaria monograficzne

Założenia (opisowo)

Wymagane jest uprzednie zaliczenie kursu Logika II na filozofii, Logika i teoria mnogości II na kognitywistyce albo innego równoważnego. Przydatna (choć niekonieczna) jest znajomość podstaw teorii obliczeń.

Efekty kształcenia

Nabyta wiedza:
- Zna podstawowe pojęcia z zakresu teorii obliczeń.
- Zna podstawowe pojęcia z zakresu teorii struktur obliczalnych oraz teorii struktur punktualnych.
- Zna różne twierdzenia dotyczące tych pojęć.
Nabyte umiejętności:
- Potrafi zrozumieć dowody korzystające z różnych typowych w teorii obliczeń metod.
- Potrafi przeprowadzać rozumowania na temat własności obliczeniowych struktur oraz relacji.
Nabyte kompetencje społeczne:
- Potrafi przedstawiać swoje argumenty.
- Potrafi analizować argumenty przedstawiane przez innych oraz się do nich odnosić.

Kryteria oceniania

Aktywność na zajęciach, w każdym semestrze wygłoszenie referatu na uzgodniony z prowadzącym
temat. W uzasadnionych sytuacjach możliwe jest zaliczenie seminarium w oparciu o pracę pisemną
zamiast referatu.

Dopuszczalna liczba nieobecności podlegających usprawiedliwieniu: 2

Literatura

C.J. Ash, J. Knight, Computable Structures and the Hyperarithmetical Hierarchy.
Nikolay Bazhenov, Rod Downey, Iskander Kalimullin, Alexander G. Melnikov, Foundations of
online structure theory. The Bulletin of Symbolic Logic (2019).
Marina Dorzhieva, Rodney Downey, Ellen Hammatt, Alexander G. Melnikov, Keng Meng Ng,
Punctually presented structures II: comparing presentations. Archive for Mathematical Logic (2024).
Herbert Enderton, A Mathematical Introduction to Logic.
J.E. Hopcroft, J.D. Ullman, Introduction to Automata Theory, Languages and Computation.
Steffen Lempp, Priority Arguments in Computability Theory, Model Theory, And Complexity Theory
(skrypt dostępny online).
Antonio Montalbán, Computable Structure Theory: Within the Arithmetic.
Abtonio Montalbán, Computable Structure Theory: Beyond the Arithmetic.
Hartley Rogers, Theory of Recursive Functions and Effective Computability.
Richard A. Shore Shore, Computable Structures: Presentations Matter (skrypt dostępny online).
Michael Sipser, Introduction to the Theory of Computation.