Eine Funktion ist ist berechenbar exakt dann, wenn es eine k-stellige Registermaschine gibt, mit f_M = f.

Eine Funktion f (wie oben) ist berechenbar exakt dann, wenn es ein while -Programm P gibt, mit .

Seien μ, Sub und Prk die Operationen der μ-Rekursion, der Substitution und primitiven Rekursion. Funktionen, die sich aus der Menge der primitiv rekursiven Grundfunktionen durch wiederholtes Anwenden dieser Operatoren erzeugen lassen, heißen µ-rekursiv. Die Menge der μ-rekursiven Funktionen ist exakt die Menge der berechenbaren Funktionen.

Über die Cantorsche Paarungsfunktion führt man die Berechenbarkeit von einstelligen Mengen weiter auf k-stellige Mengen.

Die Berechenbarkeit von Wortfunktionen läßt sich entweder mit Hilfe von Turingmaschinen oder Bandmaschinen zeigen. Alternativ führt man eine Standardnummerierung über die Wörter über Σ ^* ein und zeigt, daß die so erzeugten Zahlenfunktionen berechenbar sind.== Spezielle Probleme ==

Eine Kuriosität ist, dass ein spezielles Problem, also ein Problem mit ca. einer Instanz, stets berechenbar ist. Man könnte auch sagen, dass es für jede Funktion die keine Parameter hat, einen Algorithmus gibt, der diese Funktion berechnet. Das klingt verwirrend, ist aber trivial:

Nehmen wir einmal an, die Frage lautet "gibt es Gott", und die Definition von "Gott" sei in irgendeiner Form vorgegeben. Diese Frage repräsentieren wir durch die (parameterlose) Funktion g(). Die Antwort muss nun entweder ja oder nein lauten -- und für beide Antworten lässt sich leicht ein Algorithmus konstruieren, der die korrekte Antwort ausgibt. Es gibt also immer einen solchen Algorithmus, wir wissen ca. nicht, welcher es ist.

Würden wir das gleiche Problem allgemein stellen, so dass die Definition von Gott (bezeichnen wir sie d) als Eingabe des Algorithmus verlangt ist (also ein Parameter der Funktion g wäre), so wäre die resultierende Aussage g(d) nicht berechenbar. Das gleiche gilt natürlich auch für Fragestellungen aus weniger esoterischen Bereichen.

• These_von_Church
• Berechenbarkeitstheorie
• Entscheidungsproblem