Vergleich der Turingmaschine mit einem Computer

Aus Informatik
Wechseln zu: Navigation, Suche

Es stellt sich nun die Frage, ob denn die Turingmaschine ein Modell für einen Computer ist. Das scheint zunächst nicht der Fall zu sein: Bei der Arbeit mit Simulationsprogrammen können wir sehen, dass ein Computer eine Turingmaschine simulieren kann. Also ist ein Computer mindestens so leistungsfähig wie eine Turingmaschine. Nun soll umgekehrt einsichtig gemacht werden, dass eine Turingmaschine mindestens so leistungsfähig ist wie ein Computer. Damit ist dann die prinzipiell gleiche Leistungsfähigkeit gezeigt.

Unser Ausgangspunkt ist die Tatsache, dass Computer Algorithmen abarbeiten. Wir analysieren nun, was beim Abarbeiten eines Algorithmus geschieht, und reduzieren dies auf das Wesentliche.

Wie führt ein menschlicher Rechner etwa eine schriftliche Multiplikation aus?

Der Rechner schreibt Zeichen auf ein Ausgabemedium, z. B. Papier und löscht gegebenenfalls welche. Da der abgearbeitete Algorithmus endlich ist, sind dies stets nur endlich viele Zeichen. Wir können daher annehmen, dass die Zeichen alle aus einer vorher festgelegten endlichen Menge stammen. Im Prinzip genügt sogar ein einziges Zeichen und ein Zwischenraum als Leerzeichen.

Dies rechtfertigt die Annahme eines endlichen Alphabets.

Wir können annehmen, dass das Papier in Felder eingeteilt ist und in jedes Feld nur ein einziges Zeichen geschrieben wird. Wir können von der zweidimensionalen Anordnung der Felder auch zu einer eindimensionalen übergehen, also zu einem Band. Da die Rechnung nicht an Materialmangel scheitern soll, können wir annehmen, dass rechts und links bei Bedarf weitere Felder angefügt werden können.

Dies rechtfertigt die Annahme eines potentiell unendlichen Bands.

Die Berechnung erfolgt schrittweise. Komplizierte Operationen lassen sich in eine Folge elementarer Operationen auflösen. In jedem Arbeitsschritt wird genau eine elementare Operation ausgeführt. Eine solche ist das Lesen und Schreiben eines einzelnen Zeichens.

Der Rechner kann nur einen beschränkten Teil des Arbeitsbandes überblicken. Man kann annehmen, dass dies nur ein einziges Feld ist. Können nämlich beispielsweise 7 Felder gleichzeitig überblickt werden und sind 9 verschiedene Zeichen möglich, so fassen wir die 97 Kombinationen, die als verschieden erkannt werden, jeweils als ein einziges neues Zeichen auf und schreiben ein solches Zeichen in ein einziges Feld. Wir haben dann ein neues endliches Alphabet. Eine weitere elementare Operation ist es nun, die Aufmerksamkeit dem links oder rechts benachbarten Feld zuzuwenden.

Dies motiviert die Annahme eines Arbeitsfelds und der elementaren Operationen Lesen oder Schreiben auf dem Arbeitsfeld und Übergang zum rechten oder linken Feld.

Der Rechner verfügt über ein Gedächtnis. Dieses ist begrenzt, er darf daher Notizen auf Papier machen. Ferner ist es für die Exaktheit der Berechnung wichtig, verschiedene klar voneinander zu unterscheidende Phasen des Gedächtnisses anzunehmen. Da der Berechnungsprozess als Algorithmus endlich ist, werden nur endlich viele solche Phasen durchlaufen.

Dies motiviert die Annahme einer endlichen Zustandsmenge.

Die Berechnung erfolgt zwangsläufig. Der Rechner darf zu keinem Zeitpunkt im Zweifel sein, was er als nächstes zu tun hat, sonst könnten verschiedene Rechner zu verschiedenen Ergebnissen gelangen. Also kann man annehmen, dass die Tätigkeit des Rechners eindeutig bestimmt ist durch seinen Zustand und den Inhalt des beobachteten Feldes. Er kann in Abhängigkeit davon den Inhalt des beobachteten Feldes ändern, zum rechts benachbarten Feld übergehen, zum links benachbarten Feld übergehen oder aufhören und die Rechnung für beendet erklären.

Dies rechtfertigt die Annahme der Überführungsfunktion.

Nach solch einer Normierung des Berechnungsprozesses unterscheidet sich das Verhalten des Rechners nicht von dem einer Turingmaschine. Ein Algorithmus kann also - im Prinzip - von einer Turingmaschine abgearbeitet werden. Ein Computer ist daher nicht leistungsfähiger als eine Turingmaschine. Er arbeitet lediglich effizienter.