A Recursive Introduction to the Theory of Computation
Celem tego podręcznika jest przedstawienie teorii obliczeń.
Po wprowadzeniu pojęcia modelu obliczeń i przedstawieniu różnych przykładów, autor bada ograniczenia efektywnych obliczeń za pomocą podstawowej teorii rekurencji. Samoreferencja i inne metody są wprowadzane jako fundamentalne i podstawowe narzędzia do konstruowania algorytmów i manipulowania nimi.
Następnie książka rozważa złożoność obliczeń i wprowadza pojęcie miary złożoności. Wreszcie, książka kończy się rozważaniem miar czasu i przestrzeni oraz klasyfikacją funkcji obliczalnych jako wykonalnych lub niewykonalnych. Autor zakłada jedynie podstawową znajomość matematyki dyskretnej i informatyki, dzięki czemu podręcznik ten idealnie nadaje się na kurs wprowadzający dla absolwentów.
Jest on oparty na wielu takich kursach prezentowanych przez autora, dlatego zawiera liczne ćwiczenia. Ponadto do większości z nich dołączone są rozwiązania.
