A Recursive Introduction to the Theory of Computation
A tankönyv célja, hogy bemutassa a számításelméletet.
A számítási modell fogalmának bevezetése és különböző példák bemutatása után a szerző a hatékony számítás korlátait vizsgálja az alapvető rekurzióelméleten keresztül. Az önreferencia és más módszerek mint az algoritmusok felépítésének és manipulálásának alapvető és alapvető eszközei kerülnek bemutatásra.
Innen kiindulva a könyv a számítások bonyolultságát vizsgálja, és bemutatja a bonyolultsági mérték fogalmát. Végül a könyv az idő- és térmértékek figyelembevételével, valamint a kiszámítható függvények megvalósítható vagy nem megvalósítható kategóriákba sorolásával zárul. A szerző csak alapvető ismereteket feltételez a diszkrét matematikában és a számítástechnikában, így ez a tankönyv ideális egy felsőfokú bevezető kurzushoz.
A szerző által bemutatott számos ilyen kurzuson alapul, ezért számos feladatot tartalmaz. Ezenfelül a legtöbb ilyen feladat megoldását is közli.
