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 zu lösen?

Um Problemstellungen zu lösen, können Algorithmen nützlich sein. Dazu können Probleme in algorithmisch lösbare und unlösbare klassifiziert werden. Man spricht auch von Berechenbarkeit.

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. Auch für die Fälle, in denen \(f(m)\) nicht definiert ist, läuft der Algorithmus ab.

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

Präzisierung des Algorithmusbegriffs

Theorie Icon Der bisherige Algorithmusbegriff deckt nicht gänzlich die Frage nach der Berechenbarkeit von Funktionen ab. 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