Berechenbarkeit

Eine mathematische Funktion ist berechenbar (auch effektiv berechenbar oder rekursiv), wenn für sie eine Berechnungsanweisung (Algorithmus) formuliert werden kann (Berechenbarkeitstheorie). Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe reagiert. Der Definitionsbereich der Funktion ist die Menge der Eingaben, für die der Algorithmus eine Ausgabe produziert. Wenn der Algorithmus nicht terminiert, dann ist die Eingabe kein Element der Definitionsmenge. Dem Algorithmusbegriff liegt ein Berechnungsmodell zugrunde. Verschiedene Berechnungsmodelle sind entwickelt worden, es hat sich aber herausgestellt, dass die stärksten davon zum Modell der Turingmaschine gleich stark (Turing-mächtig) sind. Die Church-Turing-These behauptet daher, dass die Turingmaschinen den intuitiven Begriff der Berechenbarkeit wiedergeben. In der Berechenbarkeitstheorie heißen genau die Funktionen berechenbar, die Turing-berechenbar sind. Zu den Turing-mächtigen Berechnungsmodellen gehören neben der Turingmaschine beispielsweise Zweikellerautomaten, WHILE-Programme, μ-rekursive Funktionen, Registermaschinen und der Lambda-Kalkül. Zu den Berechnungsmodellen, die schwächer sind als Turingmaschinen, gehören zum Beispiel die LOOP-Programme. Diese können zum Beispiel die Turing-berechenbare Ackermannfunktion nicht berechnen. Ein dem Begriff der Berechenbarkeit eng verwandter Begriff ist der der Entscheidbarkeit. Eine Teilmenge einer Menge (zum Beispiel eine Formale Sprache) heißt entscheidbar, wenn ihre charakteristische Funktion (im Wesentlichen das zugehörige Prädikat) berechenbar ist.