Berechenbarkeit

Berechenbarkeit bezeichnet in der Informatik die Eigenschaft, dass ein mathematisches Problem oder eine Funktion durch einen Algorithmus mit festem Ablauf gelöst werden kann. Formal gefragt ist, ob es ein endliches Schritt-für-Schritt-Verfahren gibt, das für alle zulässigen Eingaben terminiert und das gewünschte Ergebnis liefert. Ziel der Berechenbarkeitsforschung ist es zu bestimmen, welche Probleme algorithmisch lösbar sind und welche nicht.

Zu den formalen Modellen der Berechenbarkeit gehören Turingmaschinen, der Lambda-Kalkül und die Theorie der rekursiven Funktionen. Diese Modelle liefern äquivalente Formalismen für das, was computierbar ist. Die Church-Turing-These fasst dies zusammen, indem sie behauptet, dass jede vernünftige Definition von Berechenbarkeit sich auf eine dieser Formalismen abbilden lässt.

Eine der bekanntesten Ergebnisse ist die Unentscheidbarkeit bestimmter Probleme. Zum Beispiel lässt sich das Halteproblem für Turingmaschinen allgemeingültig nicht entscheiden; es gibt keinen Algorithmus, der für jedes Programm und jede Eingabe bestimmt, ob das Programm jemals anhält. Ähnlich ist das Allgemeine Entscheidungsproblem der ersten Ordnung unentscheidbar. Solche Ergebnisse unterscheiden Berechenbarkeit von bloßer Lösbarkeit im Sinn der Praxis und zeigen Grenzen automatischer Methoden.

Die Unterscheidung zwischen Berechenbarkeit und Effizienz wird oft durch den Bereich der Komplexität betont. Alle berechenbaren Funktionen könnten theoretisch von Algorithmen gelöst werden, jedoch kann der benötigte Aufwand exponentiell wachsen. In der Praxis bedeutet dies, dass manche Probleme theoretisch lösbar, aber nicht praktikabel sind. Berechenbarkeit bildet damit die theoretische Grundlage der Informatik, während die Ressourcenkomplexität eine praktische Einschränkung beschreibt.

Historisch gehören Gödel, Turing und Church zu den prägenden Figuren. Die Formulierung der Church-Turing-These hat die Verbindung zwischen Maschinen-, Kalkül- und Funktionentheorie hergestellt und prägt bis heute das Verständnis dessen, was algorithmisch möglich ist.