Funkcje rekurencyjne i zagadnienia rozstrzygalności

Pojęcie obliczalności. Maszyny Turinga. Funkcje i relacje pierwotnie rekurencyjne i rekurencyjne i ich włsności. Teza Churcha. Funkcje uniwersalne. Twierdzenie Kleene'ego o postaci normalnej. Zbiory rekurencyjnie przeliczalne. Reprezentowalność funkcji rekurencyjnych w Arytmetyce Robinsona. Nierozstrzygalność i niezupełność Arytmetyki Robinsona. Teorie rozstrzygalne i metody dowodzenia rozstrzygalności teorii. Teorie nierozstrzygalne i metody dowodzenia nierozstrzygalności.

Literatura

A. Grzegorczyk, Zagadnienia rozstrzygalności, PWN 1957.
E. Mendelson Introduction to Mathematical Logic, D. van Nostrand Co. 1979.
R. Murawski, Funkcje rekurencyjne i elementy metamatematyki, Wydawnictwo Nukowe UAM, 1991.
J.R. Shoenfield, Mathematical logic, Reading, 1967.
J.R. Shoenfield, Recursion Theory, Springer-Verlag, 1993.
C. Smorynski, The Incompleteness Theorems, w Handbook of Mathematical Logic (red. J. Barwise), North-Holland, 1979.

Powrót