berechenbare

Berechenbare ist das deutsche Adjektiv für berechenbar, also fähig, durch einen Algorithmus oder eine endliche Folge von Schritten bestimmt zu werden. In der Mathematik und der theoretischen Informatik bezeichnet es Eigenschaften, die sich durch eine effektive Berechnungsmethode erschließen lassen, etwa Funktionen, Sprachen oder Entscheidungsprobleme.

Eine Funktion f: N → N ist berechenbar, wenn es eine endliche Beschreibung gibt – etwa ein Programm, eine Turingmaschine oder eine Menge rekursiver Funktionen – die bei gegebenem Input n das Endergebnis f(n) liefert und der Prozess terminiert. Allgemein unterscheidet man zwischen total berechenbaren Funktionen (der Algorithmus terminiert für alle Eingaben) und teilweise berechenbaren Funktionen (terminiert nur für bestimmte Eingaben).

Historisch entstand das Konzept im Umfeld der Grundlagen der Mathematik in den 1930er Jahren, mit Arbeiten von Alan Turing, Alonzo Church und Stephen Kleene. Verschiedene formale Modelle wie Turingmaschinen, der Lambda-Kalkül und rekursive Funktionen liefern äquivalente Vorstellungen von Berechenbarkeit. Die Church-Turing-These besagt, dass alle intuitiv berechenbaren Funktionen von diesen Modellen erfasst werden.

Im Unterschied dazu steht die Entscheidbarkeit von Problemen: Ein Problem ist entscheidbar, wenn es eine allgemeine Prozedur gibt, die für jede Eingabe zuverlässig Ja- oder Nein-Antwort liefert. Es gibt jedoch Probleme, die zwar als Funktionen berechenbar sind, deren zugehörige Ja/Nein-Frage unentscheidbar bleibt, wie das Halteproblem. In der Praxis wird der Begriff oft für konkrete Funktionen oder Sprachen verwendet.

Verwendung findet der Ausdruck in der Fachliteratur, um zu sagen, dass etwas durch einen Algorithmus berechnet oder durch eine Maschine ausgeführt werden kann. In der Alltagssprache bedeutet berechenbar oft schlicht „mit einem Computer lösbar“.