Wyd. I


Wyd. II


Wyd. III


Wyd. IV.

Roman Murawski
Funkcje rekurencyjne i elementy metamatematyki.
Problemy zupełności, rozstrzygalności, twierdzenia Gödla.
Wydawnictwo Naukowe UAM, Poznań, wydanie pierwsze 1990, wydanie drugie 1991, wydanie trzecie 2000, wydanie czwarte 2010.
186 stron

Spis treści


Przedmowa
Wstęp

Rozdział I. FUNKCJE REKURENCYJNE
    1. Pojęcie efektywności w matematyce. Funkcje obliczalne
    2. Funkcje rekurencyjne i ich własności
    3. Algorytmy Markowa i maszyny Turinga
    4. Funckje pierwotnie i elementarnie rekurencyjne
    5. Hierarchia arytmetyczna
    6. Teza Churcha
    7. Uwagi historyczne

Rozdział II. TWIERDZENIA GODLA O NIEZUPEŁNOŚCI
    1. Arytmetyka liczb naturalnych
    2. Reprezentowalność funkcji i relacji rekurencyjnych w arytmetyce
        Peano
    3. Arytmetyzacja
    4. Twierdzenia Gödla
    5. Twierdzenia Parisa-Harringtona-Kirby'ego
    6. Uwagi historyczne

Rozdział III. PROBLEM ROZSTRZYGALNOŚCI TEORII
    1. Podstawowe definicje i twierdzenia
    2. Teorie rozstrzygalne
    3. Teorie nierozstrzygalne
    4. Uwagi historyczne

Rozdział IV. KOMENTARZ FILOZOFICZNY I METODOLOGICZNY

Bibliografia
Skorowidz symboli
Skorowidz nazwisk
Skorowidz terminów