|
2.1.1 Berechenbarkeit
Die zentrale Frage der Berechenbarkeitstheorie lautet:
Gibt es prinzipielle Grenzen der Berechenbarkeit?
Die Auseinandersetzung mit dieser Frage erfordert die Kl¨
arung des Begriffes
Berechenbarkeit.
6
Hierzu sei von folgender Fragestellung ausgegangen: Ziel
ist die Berechnung einer Funktion f : M → N f¨ur zwei Mengen M und N .
Ein einfaches Beispiel hierf¨
ur ist die ¨
Uberpr¨
ufung, ob eine nat¨
urliche Zahl
eine Primzahl ist; M ist dann die Menge der nat¨urlichen Zahlen, die Ergeb-
nismenge N ist {ja, nein}. Eine m¨oglicherweise komplexere Aufgabe w¨are die
Entwicklung eines Verfahrens, das einen Text von einer Sprache in eine ande-
re ¨
ubersetzt. Eine Funktion bzw. ein Problem wird als berechenbar definiert,
wenn ein Algorithmus existiert, der f¨
ur jeden Eingabewert m ∈ M nach end-
lich vielen Schritten anh¨
alt und als Ergebnis f (m) liefert. Diese Definition
erfordert eine Auseinandersetzung mit dem Begriff Algorithmus.
Informell sei ein Algorithmus definiert als eine mit (semi-)formalen Mitteln
eindeutig beschreibbare, effektiv nachvollziehbare Verarbeitungsvorschrift zur
L¨
osung einer Klasse von Problemen im Sinne der Transformation von Ein-
gabedaten in Ausgabedaten. Es gibt verschiedenste Konkretisierungen bzw.
Formalisierungen, durch die ein Algorithmus dargestellt werden kann: Pro-
grammiersprachen (z. B. Pascal, C++, Java, C#, Smalltalk), mathemati-
sche Kalk¨
ule (z. B. µ-rekursive Funktionen), Maschinenmodelle (z. B. Turing-
Maschine, Pentium-Prozessor) usw. Damit stellt sich die Frage, inwieweit die
Berechenbarkeit eines Problems von dem verwendeten Modell abh¨
angig ist.
Es hat sich jedoch gezeigt, dass alle bisher untersuchten Konkretisierungen
des Begriffes Algorithmus gleich m¨
achtig sind im Hinblick auf die prinzipi-
elle Berechenbarkeit von Problemen. Dies wird in der Churchschen These
folgendermaßen formuliert:
Jede im intuitiven Sinne berechenbare Funktion
ist Turing-berechenbar.
Als Turing-berechenbar bezeichnet man dabei die Probleme, die auf dem klas-
sischen Maschinenmodell der theoretischen Informatik, der Turing-Maschine,
berechnet werden k¨
onnen. Anstatt dieses Modell darzustellen, sei hier ein ein-
facheres Modell zu Grunde gelegt, die WHILE-Programmiersprache, die nur
die folgenden vier Operationen umfasst:
x := 0;
x := x + 1;
x := x − 1;
while
x = y do . . . end;
6
Vgl. f¨
ur die folgenden Darlegungen z. B. Engesser (1993), Harel (2000), Rechen-
berg (2000) und Wegener (1999).
16
2. Informatik und Informations- und Kommunikationstechnik
Das heißt, man kann Variablen definieren (hier z. B. x), denen lediglich
der Wert null direkt zugewiesen werden kann. Durch zwei weitere Operatio-
nen kann der Wert einer Variablen um eins erh¨
oht bzw. verringert werden.
Operationen werden durch Semikola abgeschlossen. Die while-Operation wie-
derholt die durch do und end eingeschlossene Operationssequenz solange, wie
die zu vergleichenden Variablen ungleich sind. Man kann sich ¨
uberlegen, dass
bekannte m¨
achtigere Befehle aus diesen Elementaroperationen konstruierbar
sind. So kann man eine Addition
x := x + y;
¨
uber folgendes kurzes WHILE-Programm durchf¨
uhren:
z := 0;
while
z = y do x := x + 1; z := z + 1; end;
Nunmehr kann man Multiplikationen ¨
uber wiederholte Additionen ab-
bilden usw. Es hat sich herausgestellt, dass man die Konstrukte h¨
o-
herer Programmiersprachen auf die Elementaroperationen der WHILE-
Programmiersprache zur¨
uckf¨
uhren kann. Damit besagt obige These anschau-
lich, dass man zu jedem in irgendeiner sinnvollen Form spezifizierten Algo-
rithmus ein entsprechendes WHILE-Programm konstruieren kann, das die
gleiche Funktion berechnet. Gleichermaßen l¨
asst sich jeder in irgendeinem
Formalismus dargestellte Algorithmus in einen entsprechenden Algorithmus
eines beliebigen anderen Formalismus transformieren.
Die Churchsche These ist kein mathematischer Satz, da der Begriff der
”
im intuitiven Sinne berechenbaren Funktion“ nicht pr¨
azisiert werden kann.
Da aber bisher alle Versuche gescheitert sind, die Churchsche These zu wi-
derlegen, wird sie heute allgemein anerkannt. Man geht daher davon aus,
dass sich alle Programmiersprachen und Computermodelle hinsichtlich der
prinzipiellen Berechenbarkeit von Problemen gleichen.
Nachdem der Begriff Berechenbarkeit charakterisiert wurde, k¨
onnen wir
auf die Ausgangsfrage
”
Gibt es prinzipielle Grenzen f¨
ur Berechenbarkeit?“
zur¨
uckkommen. Ein einfaches Argument weist nach, dass Funktionen existie-
ren, die nicht berechenbar sind: Es gibt nur abz¨
ahlbar viele Algorithmen,
da alle Algorithmen als abz¨
ahlbar viele WHILE-Programme formulierbar
sind. Andererseits gibt es ¨
uberabz¨
ahlbar viele Funktionen f : M → N , wie
man ¨
uber eine einfache Diagonalisierung zeigen kann. (Die Argumentation
ist hier analog zu dem Beweis von Cantor, dass die Menge der reellen Zahlen
¨
uberabz¨
ahlbar ist, d. h. die Elemente der Menge lassen sich nicht fortlaufend
nummerieren.) Damit existieren unendlich viele solcher nichtberechenbarer
Funktionen. Das ber¨
uhmteste nichtberechenbare Problem ist das so genann-
te
Halteproblem: Gibt es ein Programm, das entscheidet, ob ein belie-
biges gegebenes Programm f¨
ur beliebige Eingabeparameter anh¨
alt
(terminiert)?
2.1 Theoretische Grundlagen
17
Man kann zeigen, dass dieses Problem in seiner Allgemeinheit nicht l¨
osbar ist;
vgl. z. B. Engesser (1993). Diese fundamentale Aussage zeigt, dass wohldefi-
nierte Probleme existieren, die aus prinzipiellen Gr¨
unden nicht l¨
osbar sind.
Im Gegensatz zu vielen anderen Problemen, die wegen ihres Umfanges o. ¨
A.
praktisch nicht l¨
osbar sind (s. u.), handelt es sich hier um eine Aussage ¨
uber
die endg¨
ultigen, praktischen wie theoretischen Grenzen des algorithmisch Be-
rechenbaren. Dieses Ergebnis hat auch weitreichende praktische Folgerungen:
So kann man etwa auch zeigen, dass kein Algorithmus existieren kann, der
Programme im Allgemeinen hinsichtlich ihrer semantischen Korrektheit ¨
uber-
pr¨
uft.
Do'stlaringiz bilan baham: | 
