Eine berechenbare Funktion (oder rekursive Funktion ) ist eine halb berechenbare Funktion (oder teilweise rekursive Funktion ), die ebenfalls vollständig ist, dh über ihre gesamte Domäne definiert ist. Dies sind die Funktionen, die von einer „terminierenden“ Turingmaschine berechnet werden .
Eine berechenbare Funktion ist nicht unbedingt „physikalisch berechenbar“, beispielsweise wenn ihre Ausführungszeit mehrere Milliarden Jahre überschreitet.
Die einfachsten Beispiele für berechenbare Funktionen sind konstante Funktionen . Eine Konsequenz des Prinzips des ausgeschlossenen Dritten ist dann, dass die konstante Funktion, die einer ganzen Zahl 1 zuordnet, wenn die Goldbach-Vermutung wahr ist, und 0, wenn sie falsch ist, berechenbar ist, obwohl wir heute nicht wissen, ob die Vermutung wahr ist. Dies zeigt, wie die Anwendung dieses Prinzips jeden intuitiven Begriff der Berechenbarkeit zerstört.