Berechenbarkeitsbegriff

Ein Problem (z.B. eine mathematische Funktion) heißt berechenbar, falls dafür ein Algorithmus existiert.

Berechenbar: Algorithmus stoppt nach endlich vielen Schritten
  Funktion f: W → V ist
- partiell: Def(f) ⊆ W (Beispiel: f: ℝ → ℝ, f(x)= 1/x)
- total: Def(f) = W

Ausgangssituation: Wir entwerfen und programmieren einen Algorithmus und wir haben eine Vorstellung was berechenbar ist (intuitiver Berechenbarkeitsbegriff). Das Problem ist nun, wie man diese Berechenbarkeit nachweisen kann. Dazu bringen wir die intuitive Form in eine mathematische Form und können diese mit mathematischen Beweisen belegen.

Formale Definitionen des Berechenbarkeitsbegriff: Turing berechenbare Funktionen, while-Programme, µ-rekursive Funktionen

Church-Turing-These

Die Klasse der Turing-berechenbaren Funktionen ist genau die Klasse der intuitiv berechenbaren Funktionen. Wobei "intuitiv" nicht exakt formalisierbar ist.

Die durchführbaren Algorithmen sind eine Teilmenge der berechenbaren Funktionen, welche wiederum eine Teilmenge aller existierenden Funktionen sind.

Beispiele

Durchführbare Algorithmen

ggT, Matrizenmultiplikation, Zinsberechnung,…

Berechenbare Funktionen, die nicht durchführbar sind

Harte Optimierungsprobleme mit Millionen von Variablen
Vollständige Eigenwertberechnung auf dem Facebook-Graphen

Nicht berechenbare Funktionen

Haltefunktion (gibt zu einem beliebigen Programm an, ob es hält)
Äquivalenzfunktion (gibt zu zwei beliebigen Programmen an, ob sie das gleiche Verhalten haben)
…

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 6.4 und 7.1 zu finden.