Struktury obliczalne i punktualne 3800-SOP25-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) Zbiory rekurencyjne, rekurencyjnie przeliczalne, algorytmicznie wyuczalne.
b) Stopnie Turinga i ich struktura.
c) Konstrukcje przekątniowe oraz priorytetowe w teorii obliczeń.
d) Elementy wiedzy o różnych typach struktur: obliczalnych, punktualnych, PTIME, automatycznych.
e) Porównywanie własności obliczeniowych punktualnych kopii liczb naturalnych z następnikiem.
f) Punktualne stopnie struktur.
g) Uczenie się struktur w stylu Golda.
h) Wstęp do rang Scotta.
Rodzaj przedmiotu
Założenia (opisowo)
Koordynatorzy przedmiotu
Efekty kształcenia
Nabyta wiedza:
- Zna niektóre własności struktury stopni Turinga.
- Zna podstawowe pojęcia z zakresu teorii struktur obliczalnych oraz teorii struktur punktualnych.
- Zna podstawowe twierdzenia dotyczące tych pojęć.
- Zna pojęcie rangi Scotta.
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.
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: