Was können Computermedien? Gibt es prinzipielle Grenzen für das, was Computer z.B. mit Texten, Bildern und Klängen anstellen können? Hängt das von der Rechnerleistung ab? Ist ihr Horizont prinzipiell offen oder abgeschlossen?
Zur Beantwortung dieser Frage muß geklärt werden, wie Rechneraktivität präzise beschrieben werden kann, was Rechnen und Berechenbarkeit -- damit auch Bearbeitung von kodierten Sinnesdaten wie in der digitalen Medientechnik -- eigentlich heißt.
Dazu wird ein Maschinenmodell des Rechnens vorgestellt -- das der Turing-Maschine --, aus den Folgerungen für die obigen Fragen gezogen werden.
Wenn im folgenden von einer Zahl die Rede ist, kann man sich, wenn man will, natürlich auch vorstellen, diese Zahl sei der Kode einer Nachricht, die zu bearbeiten ist, Rechnen und Bearbeiten kodierter Sinnesdaten wie in der Medientechnik sind damit dasselbe.
Definition: eine Zahl heißt berechenbar, wenn jede ihrer Ziffern in Stellenwertschreibweise mit endlichen Mitteln von einer Maschine berechnet und notiert werden kann.
Was heißt das?
1. Eine Maschine soll das tun, kein Mensch oder eine andere äußere Instanz soll an dem Prozeß beteiligt sein.
2. Eine Zahl kann durchaus unendlich viele Ziffern haben, etwa
Pi = 3,14159265358979... ,
dennoch soll für ihre Berechenbarkeit genügen, daß jede beliebige Stelle, die 3. oder auch die 6.395.280.194-te oder irgendeine andere, irgendwann tatsächlich auch von der Maschine niedergeschrieben werden kann. Das kann im Einzelfall sehr lange dauern, nur muß es tatsächlich auch geschehen können. Die Zahl muß also effektiv, nicht effizient aufzuschreiben sein.
3. Endliche Mittel muß heißen: die Beschreibung des Verfahrens ist endlich, es kommt nicht immer wieder etwas hinzu, die verbrauchten Ressourcen, etwa Papier zum Notieren von Ergebnissen, sind endlich, ohne daß eine willkürliche Grenze gesetzt werden soll (etwa: 1000 Seiten), die verwendeten unterschiedlichen Symbole sollen nur endlich viele sein -- z.B. 0 und 1 --, also auch hier sollen nicht irgendwann neue hinzukommen dürfen.
4. Die Maschine soll aus sich heraus rechnen, d.h. ihr soll nur das Verfahren mitgeteilt werden, nicht schon das Ergebnis oder Teile davon.
Alan Turing hat 1937 eine solche Maschine vorgeschlagen (Turing, A.M.: On Computable Numbers, with an Application to the Entscheidungsproblem. Proc. of the London Math. Society, 2(42), (1937). (deutsch in Dotzler, B. und Kittler, F. (Hrsg.): Alan Turing -- Intelligence Service, Berlin: Brinkmann und Bose 1987. S 17-60)). Und er hat weitreichende Folgerungen aus seiner Konstruktion ziehen können‚ die hier auch zur Sprache kommen sollen.
Turing hat eine Maschine vorgeschlagen, deren Aufbau möglichst einfach sein sollte, die die Klärung der angesprochenen prinzipiellen Fragen klären sollte, sie sollte nicht wirklich gebaut werden, sie sollte auch nicht irgendwie besonders leistungsfähig in technischer Hinsicht sein.
Zwei Eigenschaften dieser Maschine seien schon jetzt erwähnt, weil sie ihre Bedeutung für die Diskussion der aufgeworfenen Fragen verdeutlichen:
Eine Turingmaschine ist folgendermaßen aufgebaut:
Man kann sich folgende schematische Vorstellung machen (der Einfachheit halber soll das Alphabet nur aus Eins und dem leeren Feld bestehen):
Der Schreib- und Lesekopf befindet sich über der dritten Eins von links, die Maschine kann nun schreiben, löschen, sich bewegen, den Zustand wechseln.
Beispiel: eine Zählmaschine
Grundlage des Zählens sei eine Reihe von Einsen auf dem Band. Dieser soll eine weitere Eins hinzugefügt werden. Die Maschine soll sich im Zustand 0 befinden, der Schreib- und Lesekopf sei irgendwo links von der Reihe von Einsen.
Verhaltenstabelle
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sie beherrscht die Grundrechenarten, denn aus dem Zählen läßt sich die Addition entwickeln, aus dieser die Multiplikation, aus dem Herunterzählen die Subtraktion und die Division. Man kann ihr Berechnungsverfahren vorschreiben, die die übliche Schulmathematik umfassen. Man kann sie ausführen lassen, was auch andernorts als überhaupt nach formalen Regeln berechenbar gilt (Church-Turing-These).
Weiteres Beispiel: Inversion eines Bildes
Sei eine Bildkodierung wie im Abschnitt "Digital und Analog" mit einer Reihe von Nullen und Einsen gegeben. Wie sieht die Turingmaschine aus, die von dem Bild das Negativ herstellt?
|
|
|
|
|
|
|
|
|
|
Die Frage nach der Berechenbarkeit läßt sich nun noch einmal anders beantworten:
Eine Zahl heißt berechenbar (oder analog: eine Menge kodierter Sinnesdaten automatisch erzeugbar), wenn eine Turingmaschine sie Ziffer für Ziffer auf ein anfangs leeres Band schreiben kann.
Im Zusammenhang mit digitaler Medientechnik kann diese Frage auch gelesen werden als: welche Kodierungen von Sinnesdaten -- Bilder, Klänge, Texte -- sind automatisch von einem Computer erzeugbar?
Antwort: Es gibt höchstens so viele berechenbare Zahlen, wie es Turingmaschinen gibt. Dabei spielt eigentlich nur die Verhaltenstabelle der Turingmaschine eine Rolle, sie bestimmt vollständig das Verfahren und damit auch die Zahl selbst, die berechnet wird.
Wie viele Turingmaschinen und berechenbare Zahlen gibt es?
Antwort: es gibt unendlich viele, aber man kann sie durchnumerieren. Es gibt abzählbar unendlich viele Turingmaschinen und damit auch abzählbar unendlich viele berechenbare Zahlen.
Das Numerierungsverfahren der Turingmaschinen geht so:
|
|
|
|
|
1 |
### ...### |
0,*** ...**** ...***... |
|
2 |
#####..### |
0,*****...******...*****... |
|
... |
... |
... |
|
k |
#####...#######...#######...### |
0,******...***...******... |
|
... |
... |
... |
Gibt es Zahlen, die sich nicht von einer Turingmaschine -- also überhaupt nicht mittels streng formaler Verfahren -- berechnen lassen? Oder anders gefragt: Gibt es Nachrichten, die ein Computer aus sich heraus nicht aufschreiben kann?
Antwort: ja. Gleich wird eine solche Zahl (oder eine solche Nachricht) konstruiert.
Dazu noch einmal die numerierte Liste der berechenbaren Zahlen (automatisch aufschreibbaren Nachrichten):
|
Nr. |
berechenbare Zahl |
||||||
|---|---|---|---|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
... |
|
|
|
|
|
|
|
|
k |
|
|
|
|
|
|
|
|
... |
|
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
... |
|
|
|
|
|
|
|
Also ist etwa ihre erste Stelle von der ersten Stelle der ersten berechenbaren Zahl verschieden, ihre zweite von der zweiten der zweiten Zahl, die k-te von der k-ten der k-ten Zahl u.s.w.
N ist also nicht in der Liste enthalten, denn in wenigstens einer Ziffer unterscheidet sie sich von allen der Zahlen in der Liste.
(Wer's noch nicht einsieht: wenn sie doch in der Liste wäre, hätte sie eine Nummer, etwa 3.026.883. Die 3.026.883-te Ziffer der Zahl an dieser Position wäre Z3.026.883,3.026.883. Aber N, die Zahl, von der gerade angenommen wurde, sie sei in der Liste, hat per Konstruktion gerade dann dort eine Eins, denn die 3.026.883-te eine Null dort hat und eine Null, wenn die 3.026.883-te dort eine Eins zu stehen hat. Also ist diese Zahl an dieser Stelle in der Liste nicht N, N steht überhaupt nicht auf der Liste der berechenbaren Zahlen, ist also selbst nicht berechenbar.)
Eine wesentliche Fragestellung für Turingmaschinen -- und auch für jedes Programm auf einem modernen Computer -- ist, ob das Programm auch wirklich eine Ausgabe liefert, oder als Totschleife in einem infiniten Regreß hängenbleibt. Für die Turingmaschinen formuliert kann man also das Problem folgendermaßen formulieren:
Kann man entscheiden, ob eine Turingmaschine für alle möglichen Bandinhalte, die ihr übergeben werden, auch tatsächlich hält? Ist diese Frage auch von einer Turingmaschine selbst endscheidbar, also durch ein streng formales Verfahren der Berechnung zu klären?
An dieser Stelle wird sich deutlich zeigen, wie die Situation der Abgeschlossenheit und Endlichkeit, die Voraussetzung für den präzisen Begriff der Berechenbarkeit ist, zu einem geschlossenen Horizont führt, dazu, daß fragen zwar in einem präzisen Begriffsapparat zwar gestellt, aber nicht immer auch beantwortet werden können. Es ist dies das Entscheidungsproblem, das Hilbert um die Jahrhundertwende noch für lösbar hielt, Turing hat gezeigt, daß dem nicht so ist.
Die Antwort lautet nämlich: nein, es gibt keine Turingmaschine, es kann keine geben, die für alle Turingmaschinen berechnet, ob diese mit jedem denkbaren Bandinhalt halten oder ob sie steckenbleiben und denmach Totschleifen sind.
Der Nachweis geht so:
Zunächst nimmt man an, es gebe doch eine solche Turingmaschine, dann zeigt man, daß diese Annahme zu absurden Konsequenzen und Widersprüchen führt, man die Annahme also fallen lassen muß.
Also: es gebe diese Turingmaschine, ich nenne sie H. Sie soll auf ihr Band eine 0 schreiben, wenn sie für die Turingmaschine N findet, daß sie eine Totschleife ist (H(N)=0), und sie schreibt eine 1, wenn sie für die Maschine N für alle Eingabewerte die Terminiertheit feststellt (H(P)=1).
Nun erfindet man eine zweite Maschine, nennen wir sie P. Für P stellt H fest, ob sie terminiert oder nicht, welchen Befund sie erhebt, spielt keine Rolle; nur, daß sie in jedem Falle die Frage der Terminierung entscheiden kann. H(P) ist eine ganz gewöhnliche berechenbare Zahl, sie hat den Wert Null oder 1. Nun kommt der Trick, die selbstreflexive Anwendung von H auf sich selbst.
P soll nämlich so gebaut werden -- und es ist entscheidend einzusehen, daß das immer geht -- daß P eine Totschleife ist, wenn H(P)=1 und terminiert, wenn H(P)=0.
Als Flußdiagramm kann das z.B. so aussehen:
Da H(P) eine berechenbare Zahl ist, ist auch P vollständig definiert. Das Berechnungsverfahren, das hinter P steckt, ist sehr einfach, es stützt sich lediglich auf den Umstand, daß H(P) wohlbestimmt ist, daß H für jede Turingmaschine Terminiertheit oder ihr Gegenteil entscheiden kann. P ist also baubar.
Nun kommt die Zwickmühle:
H(P) kann nur einen von zwei Werten haben:
Ann. 1: H(P) = 1
Dann ist P offenbar eine Totschleife, es erfolgt sofort der
Rücksprung nach oben, der Test, ob H(P) Eins sei, wird erneut
ausgeführt, und so ad infinitum. Deshalb muß H, unsere
Turingmaschine, die das Halteproblem löst, auf Totschleife
plädieren, also den Wert 0 schreiben, also
H(P)=0, im
Widerspruch zu Annahme 1.
Ann. 2: H(P) = 0
P ist dann offenbar ein terminierendes Programm, das sofort
nach der Prüfung auf den Wert von H(P) anhält. H muß
also Terminiertheit diagnostizieren, was auf
H(P)=1
herausläuft: Widerspruch.
Mit anderen Worten: die Annahme, es könnte eine Turingmaschine geben, die über alle Turingmaschinen, inklusive sich selbst, alle Entscheidungen treffen kann, die in Begriffen von Turingmaschinen wohldefiniert sind, muß fallengelassen werden. Man kann zwar Fragen sehr präzise stellen, sie aber dann im Rahmen genau dieses Begriffsrahmens möglicherweise nicht beantworten.
Das Halteproblem wirft solch eine Frage auf, die Turingmaschinen, also Computer, nicht beantworten können: Computer können nicht alles, sie können vor allem bestimmte Fragen über sich selbst nicht beantworten.
Entwerfen Sie eine Turingmaschine, die ein in Form von Nullen und Einsen kodiertes Graustufenbild (wie aus Aufgabe 1) invertiert. Die Maschine soll irgendwo links von der Kodierung des Bildes auf dem leeren Teil des Bandes stehen, dann nach rechts rücken können, um das Bild zu finden, es dann invertieren und wieder zurück auf das leere Band rücken und dort anhalten.
http://www.turing.org.uk/turing/ maintained by Andrew Hodges