Chapter 1. Előszó

Jelen jegyzet a Debreceni Egyetemen tartott Számításelmélet kurzushoz, annak anyagára épülve készült. A kurzusnak - és ennek megfelelően a jegyzetnek is - alapvető célja, hogy a hallgatók megfelelő háttértudáshoz jussanak a kiszámíthatóság- és bonyolultságelméleti alapfogalmakból.

A 2. fejezet az általános algoritmikus feladat és a Turing-gép megfogalmazásához szükséges formális nyelvekkel kapcsolatos fogalmakat ismerteti.

A 3. fejezetben a bonyolultságelméletben alkalmazandó, függvények növekedési rendjével kapcsolatos definíciók és tulajdonságok találhatók.

A 4. fejezet a Turing-gép definícióját és a hozzá kapcsolódó alapvető ismereteket tárgyalja. Itt kerül ismertetésre a Turing-gépek számításának fogalma, a Church-Turing tézis, a Turing-gépek összefűzésének elmélete, a több szalagos Turing-gépek definíciója és a hozzá kapcsolódó szimulációs tételek.

Az 5. fejezetben a kiszámíthatóságelmélettel találkozhatunk, ahol a rekurzivitást, rekurzív felsorolhatóságot és ezek kapcsolatát vizsgáljuk. A fejezet végén az eldönthetőségi problémákról esik szó.

A 6. fejezet a nemdeterminisztikus Turing-gépekkel kapcsolatos definíciókkal és alapvető tulajdonságokkal, valamint a modell Turing-ekvivalenciájával foglalkozik.

A 7. fejezetben az idő-, tár- és programbonyolultságról, a velük definiálható bonyolultsági osztályokról és kapcsolatukról esik szó.

A 8. fejezet az nyelvosztályhoz köthető eredményeket tárgyalja, többek között a tanú tételt és az -teljességgel kapcsolatos legfontosabb ismereteket.