Berechenbarkeit

Die Frage, welche Funktionen und Probleme überhaupt algorithmisch lösbar sind. Turing-, WHILE- und GOTO-Berechenbarkeit sind gleichwertig (Churchsche These), und manche praktisch wichtigen Probleme sind prinzipiell unentscheidbar.

Berechenbarkeitsmodelle

(Quelle - Automatentheorie Zusammenfassung)

Churchsche These

Turing-, WHILE- und GOTO-berechenbare Funktionen sind dieselben, und genau sie sind die im intuitiven Sinn berechenbaren Funktionen. Die These ist nicht beweisbar (intuitiv ist kein formaler Begriff), wird aber akzeptiert, weil alle bisher vorgeschlagenen Modelle sich als gleichwertig erwiesen haben. Gängige Programmiersprachen (Pascal, C, C++) sind in diesem Sinn vollständig (Quelle - Automatentheorie Zusammenfassung).

• Kleenesche Normalform: Jede berechenbare Funktion kommt mit einer einzigen while-Schleife aus.

Praktische Folgen

• WHILE = GOTO: Sprünge sind überflüssig. Sequenz, Selektion und Wiederholung reichen für alles Berechenbare. Das ist die theoretische Basis der strukturierten Programmierung der 1970er Jahre (Pascal-Familie) gegen „Spaghetti-Code“.
• LOOP ⊊ WHILE: Die Ackermannfunktion ist total und berechenbar, aber nicht LOOP-berechenbar. Eine Sprache, die nur Zählschleifen kennt, ist also nicht vollständig.

Entscheidbarkeit

• Entscheidbar (rekursiv): Ein Algorithmus antwortet für jedes Wort mit Ja oder Nein.
• Semi-entscheidbar (= rekursiv aufzählbar, Typ 0): Der Algorithmus hält bei Ja, bei Nein hält er eventuell nie.
• Unentscheidbar für vollständige Programmiersprachen (Quelle - Automatentheorie Zusammenfassung):
  • Halteproblem: Hält Programm P bei Eingabe x?
  • Korrektheitsproblem: Berechnet P die spezifizierte Funktion?
  • Äquivalenzproblem: Berechnen zwei Programme dasselbe?
  • Postsches Korrespondenzproblem: Wichtig, weil sich viele andere Probleme darauf reduzieren lassen.
• Es gibt Sprachen, die weder durch Grammatiken erzeugbar noch von Turingmaschinen akzeptierbar sind (Abzählbarkeitsargument → Chomsky-Hierarchie).

Beispiele aus der Quelle

• Programmiersprache TURING (S. 42): elementare Anweisungen Bandᵢ := 0, Bandᵢ := Bandᵢ + 1, Bandᵢ := Bandᵢ − 1, dazu Sequenz, if Bandᵢ = 0 then … else … endif und while Bandᵢ ≠ 0 do … endwhile. Beispielprogramme berechnen mult (wiederholtes Addieren) und exp (wiederholtes Multiplizieren). Ein Programm ist zugleich Syntax (Zeichenkette) und Semantik (berechnete Funktion f_P).

• WHILE simuliert LOOP (S. 44): x_j := x_i; while x_j ≠ 0 do x_j := x_j − 1; A endwhile. Umgekehrt geht das nicht, weil bei LOOP die Anzahl Durchläufe vor Beginn feststeht, bei WHILE nicht.

• Ackermannfunktion (S. 46): ack(x) = ackₓ(x). Es gilt ack(2) = 4, ack(3) = 16, ack₂(x) = 2ˣ und ack₃(x) = iter₂(x), die x-mal iterierte Zweierpotenz (iter₂(0) = 1, iter₂(n+1) = 2^iter₂(n)). Die Funktion wächst schneller als jede LOOP-berechenbare Funktion.

• Entscheidbar vs. semi-entscheidbar (S. 48): Entscheidbarkeit einer Sprache und Berechenbarkeit einer Funktion lassen sich ineinander übersetzen (charakteristische Funktion bzw. Graph {(x, y) | f(x) = y}).

  Sprachen	Probleme	Mengen
  Wortproblem entscheidbar	total berechenbar	rekursiv
  Wortproblem semi-entscheidbar (Typ 0)	teilweise berechenbar (nur die positive Antwort)	rekursiv aufzählbar
  nicht semi-entscheidbar	nicht partiell berechenbar	(übrige abzählbare und überabzählbare Mengen)

  Problem	semi-entscheidbar?	entscheidbar?
  Halteproblem	ja	nein
  Korrektheitsproblem	nein	nein
  Äquivalenzproblem	nein	nein
  Postsches Korrespondenzproblem (PCP)	ja	nein

Verwandt

• Turingmaschine – das Referenzmodell
• Komplexitätstheorie – nicht nur ob, sondern wie aufwendig
• Chomsky-Hierarchie – Entscheidbarkeit des Wortproblems je Sprachklasse