RAČUNARSKA TEORIJA

Predgovor

Glava 1 Malo čiste matematike

Skupovi i n-torke

Funkcije

Azbuke, riječi, jezici

Predikati

Kvantifikatori

Dokazivanje kontradikcijom

Matematička indukcija

Glava 2 Programi i izračunljive funkcije

Programski jezik S

Primjeri programa u jeziku S

Sintaksa jezika S

Izračunljive funkcije

Makro instrukcije

Glava 3 Primitivno rekurzivne funkcije

Kompozicija

Rekurzija

PRZ klase funkcija

Neke primitivno rekurzivne funkcije

Primitivno rekurzivni predikati

Iteracije i ograničeni kvantifikatori

Minimalizacija

Glava 4 Univerzalni program

Kodiranje parova i Gedelovi brojevi

Kodiranje programa brojevima

Problem završetka rada programa (HALTING)

Univerzalnost

Teorema o parametru

Teorema o rekurziji

Glava 5 Izračunavanje na riječima

Numeričko predstavljanje rijči

Programski jezik za rad sa riječima

Veza između jezika S i jezika Sn

Post-Tjuringov program

Simulacija Sn u T

Simulacija T u Sn

Glava 6 Tjuringova mašina

Unutrašnja stanja

Univerzalna Tjuringova mašina