Dieses Kapitel führt die Begriffe der Berechenbarkeit, Entscheidbarkeit und Semi-Entscheidbarkeit ein, zunächst informell und dann formal über Turing-Maschinen. Behandelt werden anschließend das Halteproblem, die Unentscheidbarkeit der Prädikatenlogik und die NP-Vollständigkeit des Erfüllbarkeitsproblems der Aussagenlogik.