Berechenbarkeit
Eine Funktion heißt berechenbar, wenn es einen Algorithmus gibt, etwa in einer Programmiersprache, der bei Eingabe von in endlicher Zeit berechnet; d.h. der Algorithmus terminiert. Ist nicht definiert, so folgt dann eine Endlosberechnung.
Eine Kuriosität ist, dass ein spezielles Problem, also ein Problem mit nur einer Instanz, immer 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 From 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 nur nicht, welcher es ist.
Würden wir das gleiche Problem allgemein stellen, so dass die Definition von Gott (nennen 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.Spezielle Probleme