| Előszó a könyv magyar kiadásához | 9 |
| Előszó | 11 |
| Parciális rekurzivitás | 13 |
| Rekurzív függvények | 13 |
| Algoritmusok, rekurzivitás, kiszámíthatóság | 13 |
| Parciális rekurzív függvények | 17 |
| Rekurzió és iteráció | 22 |
| Függvényegyenletek és a McCarthy-formalizmus | 25 |
| A regisztergépek | 35 |
| A regisztergépek programjai | 35 |
| Kiszámítási sorozatok | 39 |
| A regisztergép aritmetizálása | 45 |
| A Turing-kiszámíthatóság | 47 |
| A Turing-gépek | 47 |
| Felhasznált erőforrások | 54 |
| Eldönthetetlenségi fokozatok | 59 |
| Irodalmi megjegyzések | 66 |
| Szubrekurzivitás | 68 |
| A rekurzív függvények bonyolultsága | 68 |
| A bonyolultság eltérő fogalmai | 68 |
| A primitív rekurzió | 70 |
| Többszörös rekurzió | 75 |
| A Grzegorczyk-hierarchia | 78 |
| A primitív rekurzív függvények növekedési gyorsasága | 78 |
| Grzegorczyk-osztályok | 82 |
| A Grzegorczyk-osztályok és a Turing-gépek | 90 |
| Egy szubrekurzív nyelv | 95 |
| Primitív rekurziók egymásba skatulyázása | 95 |
| A LOOP nyelv | 97 |
| Ciklusmélységi osztályok | 104 |
| A ciklusmélységi osztályok és a Grzegorczyk-osztályok kapcsolata | 110 |
| Elemi függvények és operátorok | 118 |
| A szubrekurzív függvényosztályok eldönthetetlenségi kérdései | 118 |
| Elemi függvények | 121 |
| Elemi operátorok és korlátozott nyelvek | 126 |
| Irodalmi megjegyzések | 130 |
| Axiomatikus bonyolultságelmélet | 132 |
| A kiszámítási bonyolultság tanulmányozásának elvont megközelítése | 132 |
| Absztrakt bonyolultsági osztályok | 132 |
| A bonyolultsági mérték axiómái | 136 |
| A kiszámítási bonyolultság invarianciája | 145 |
| Tetszőlegesen bonyolult és tetszőlegesen felgyorsítható algoritmusú függvények | 150 |
| Bonyolultsági osztályok és a függvények bonyolultság szerinti rendezése | 150 |
| Tetszőlegesen bonyolult függvények szerkesztése | 153 |
| Optimális programok létezésének kérdése | 160 |
| A bonyolultsági osztályok elmélete | 169 |
| Hézagok a bonyolultsági osztályok között | 169 |
| A bonyolultsági osztályok "rendes" nevei | 173 |
| A Grzegorczyk-osztályok mint bonyolultsági osztályok | 182 |
| A programok hosszúsága | 189 |
| További megjegyzések a szubrekurzív nyelvekről | 189 |
| A programhosszúság axiómái | 191 |
| Programhosszúság és hatékonyság a szubrekurzív nyelvekben | 194 |
| Irodalmi megjegyzések | 200 |
| Az elemi függvények bonyolultsága | 204 |
| Konkrét problémák bonyolultsága | 204 |
| Általános megjegyzés | 204 |
| A kiszámítási idő korlátozása | 209 |
| Egyes problémák osztályozása | 217 |
| Elemi függvényosztályok | 221 |
| A szubelemi osztályok jellemzése | 221 |
| Egyszerű függvények | 226 |
| A Ritchie-Cleave hierarhia | 230 |
| Problémák visszavezetése más problémákra | 236 |
| A relatív bonyolultság | 236 |
| Reducibilitás és bonyolultsági fokozatok | 240 |
| A polinomiálisan teljes fokozat | 244 |
| Irodalmi megjegyzések | 250 |
| Irodalom | 255 |
| Tárgymutató | 265 |
