Algorithmen sind allgemeine Verfahren

Wie eingangs erwähnt wurde, sind Algorithmen allgemeine Verfahren, die eine beliebige Probleminstanz einer Klasse K von Problemen lösen können.^4.10 Bei der formalen Behandlung von Algorithmen, das heißt in der Algorithmentheorie, beinhaltet eine solche Klasse K stets abzählbar unendlich viele Probleminstanzen. Beispiele für solche Problemklassen sind:

• Entscheiden, ob eine gegebene Menge von logischen Formeln widerspruchsfrei ist.
• Entscheiden, ob ein gegebener Graph eine Clique von mindestens k Knoten enthält.^4.11

Dieser Sachverhalt spielt eine ganz entscheidende Rolle für viele Aussagen, Definitionen und Theoreme in der Algorithmentheorie. Beispielsweise basiert die bekannte Unentscheidbarkeit^4.12 bzw. Semientscheidbarkeit^4.13 der Prädikatenlogik erster Stufe darauf, daß die Klasse möglicher Formelmengen, für die der gesuchte Algorithmus eine korrekte Antwort finden soll, unbeschränkt ist. Wäre die Klasse von Formelmengen, für die ein Algorithmus korrekt arbeiten soll, endlich, so gäbe es immer einen Algorithmus. Im Extremfall könnte man einfach ein Verfahren angeben, das die richtige Entscheidung für jede erlaubte Eingabe in einer riesigen Tabelle gespeichert hat. Dann müßte der Algorithmus lediglich in der Tabelle den passenden Eintrag aufsuchen und ihn als Antwort ausgeben. Wenn man jedoch im Gegensatz dazu beliebige Formelmengen als Probleminstanzen zuläßt, so kann man zu jeder endlichen Tabelle, die ein Algorithmus A benutzt, Formelmengen konstruieren, die der Algorithmus A nicht korrekt entscheiden kann.

Es liegt also die folgende Situation vor: Zu jeder endlichen Menge Mvon Probleminstanzen gibt es einen (endlichen) Algorithmus A, der jedes Problem $P\in M$ richtig löst. Hingegen gilt umgekehrt - für unentscheidbare Problemklassen M - daß zu jedem (endlichen) Algorithmus A mindestens eine Probleminstanz $P\in M$ existiert, die A nicht korrekt lösen kann.

Um eine einheitliche Betrachtungsweise für beliebige Algorithmen zu ermöglichen, wird im folgenden der Begriff einer universellen Turingmaschine vorgestellt.