Berechenbarkeit
Die theoretische Informatik beschäftigt sich mit der Frage:
Man kann die Frage umformulieren zu:
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
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.