Berechenbarkeit

Theorie Icon Die theoretische Informatik beschäftigt sich mit der Frage:

Können mit Algorithmen buchstäblich alle Probleme gelöst werden?

Man kann die Frage umformulieren zu:

Existiert zu jedem Problem ein Algorithmus, um dieses Problem zu lösen?

Hierfür verwenden wir den Begriff der Berechenbarkeit. Die Theorie der Berechenbarkeit hat Methoden zur Klassifizierung von Problemen in algorithmisch lösbare und algorithmisch unlösbare entwickelt.

Definition

Eine Funktion heißt berechenbar, wenn es einen Algorithmus gibt, der für jeden Eingabewert \(m \in M\), für den \(f(m)\) definiert ist, nach endlich vielen Schritten anhält und als Ergebnis \(f(m)\) liefert. In allen Fällen, in denen \(f(m)\) nicht definiert ist, bricht der Algorithmus nicht ab.

Anschaulich gesprochen ist eine Funktion berechenbar, wenn man sie programmieren kann.

Präzisierung des Algorithmusbegriffs

Theorie Icon Um Fragen, wie die zur Berechenbarkeit von Funktionen zu beantworten, ist der bisherige betrachtete Algorithmusbegriff nicht präzise genug. Wir benötigen eine Definition mit dem Anspruch der mathematischen Exaktheit, um die Möglichkeiten und Grenzen von Algorithmen zu untersuchen. Hierfür gibt es verschiedene Ansätze wie Allgemein-rekursive Funktionen, das Lambda-Kalkül oder die Turingmaschine.

Mit Turingmaschinen wollen wir uns in diesem Modul genauer beschäftigen.

Übung