Berechenbaren

Berechenbarkeit, im Deutschen oft als computability in der theoretischen Informatik bezeichnet, beschreibt die Eigenschaft einer Funktion oder eines Problems, durch ein effektives Verfahren berechenbar zu sein. Das Adjektiv berechenbar wird in flektierter Form wie berechenbaren verwendet, zum Beispiel in berechenbaren Funktionen oder berechenbaren Problemen.

Definition und Modelle: Ein Objekt gilt als berechenbar, wenn es durch einen Algorithmus gelöst werden kann, der für jede zulässige Eingabe garantiert terminiert und das korrekte Ergebnis liefert. In der theoretischen Informatik existieren mehrere formale Modelle, die dasselbe Konzept der Berechenbarkeit formalisieren: Turingmaschinen, der λ-Kalkül und die μ-Rekursion. Der Church-Turing-These zufolge fassen diese Modelle die Klasse der berechenbaren Funktionen vollständig zusammen.

Kategorien: Entscheidbarkeit und Rekursivität. Ein Problem ist entscheidbar, wenn es einen Algorithmus gibt, der für alle Eingaben in endlicher Zeit mit ja oder nein antwortet. Ein Problem ist rekursiv aufzählbar (semi-entscheidbar), wenn eine Methode existiert, die bei positiven Instanzen hält, bei negativen Instanzen jedoch möglicherweise nicht terminiert.

Beispiele: Grundlegende Rechenoperationen wie Addition oder Multiplikation sind berechenbar. Das Halteproblem ist hingegen nicht berechenbar.

Historischer Kontext und Bedeutung: Die Arbeiten von Gödel, Turing, Church und Kleene führten zur formalen Definition von Berechenbarkeit. Sie bildet die Grundlage der theoretischen Informatik, insbesondere der Theorie der Komplexität, der Verifikation von Algorithmen und der Identifizierung von Grenzen des algorithmischen Wissens.