
Das Konzept der Turing-Maschine ist eine von vielen äquivalenten Formulierungen dessen, was wir unter „effektive Prozedur“ oder „Berechnung“ verstehen. Es konnte nichts mächtigeres als eine Turing-Maschine gefunden werden, das die Bedeutung derartiger Begriffe besser auf sich vereinigt (vgl. Kapitel 17). Und trotzdem gibt es Grenzen für die Mächtigkeit von Turing-Maschinen, Probleme, welche die Turing-Maschine nicht lösen kann. Diese Probleme gleichen denen, für die es keine effektive Prozedur oder rekursive Berechnung gibt. Tatsächlich kann man ein Turing-unlösbares Problem in ein Problem umformulieren, das in jedem der äquivalenten formalen Systeme unlösbar ist.