GMU:My favorite things/Projekte/Erlebbare Turingmaschinen: Difference between revisions
(Created page with "'''Erlebbare Turingmaschinen'''<br/> Moritz Dreßler, Oktober 2011 Vielen NichtinformatikerInnen fällt es schwer, das Konzept einer Turingmaschine nachzuvollziehen, auch oder g...") |
No edit summary |
||
| Line 11: | Line 11: | ||
==Aufbau== | ==Aufbau== | ||
[[Image:Md-turing-aufbau.png|thumb|Abbildung 1: Schematische Darstellung einer Turingmaschine]] | |||
Eine Turingmaschine besteht aus einem unendlichen und in gleichgroße Felder eingeteilten Speicherband, einem entlang des Bandes beweglichen Schreib- und Lesekopf sowie einem Programm zur Steuerung des Kopfes (vgl. Abbildung 1). | Eine Turingmaschine besteht aus einem unendlichen und in gleichgroße Felder eingeteilten Speicherband, einem entlang des Bandes beweglichen Schreib- und Lesekopf sowie einem Programm zur Steuerung des Kopfes (vgl. Abbildung 1). | ||
| Line 34: | Line 36: | ||
==Programm== | ==Programm== | ||
[[Image:Md-turing-programm.png|thumb|Abbildung 2: Sortieralgorithmus für eine Turingmaschine]] | |||
Ein Programm für eine Turingmaschine lässt sich als Tabelle darstellen und soll hier am Beispiel eines Sortieralgorithmus gezeigt werden (Siehe Abbildung 2). Mit Hilfe dieses Algorithmus lässt sich eine zufällige und beliebig lange Reihe von zwei verschiedenen Zeichen (hier 0 und 1) in eine Ordnung bringen (hier von links nach rechts erst 0 dann 1). Die zu sortierende Reihe muss hierbei von leeren Feldern eingeschlossen sein, damit die Turingmaschine weiß, wo die Reihe anfängt und aufhört. | Ein Programm für eine Turingmaschine lässt sich als Tabelle darstellen und soll hier am Beispiel eines Sortieralgorithmus gezeigt werden (Siehe Abbildung 2). Mit Hilfe dieses Algorithmus lässt sich eine zufällige und beliebig lange Reihe von zwei verschiedenen Zeichen (hier 0 und 1) in eine Ordnung bringen (hier von links nach rechts erst 0 dann 1). Die zu sortierende Reihe muss hierbei von leeren Feldern eingeschlossen sein, damit die Turingmaschine weiß, wo die Reihe anfängt und aufhört. | ||
Revision as of 11:01, 9 November 2011
Erlebbare Turingmaschinen
Moritz Dreßler, Oktober 2011
Vielen NichtinformatikerInnen fällt es schwer, das Konzept einer Turingmaschine nachzuvollziehen, auch oder gerade weil das Prinzip eines Algorithmus auf Unverständnis stößt. Im Folgenden soll die Idee einer erlebbaren Turingmaschine erläutert werden, in der Interessierte selbst einen Teil der Aufgaben der Maschine übernehmen, um dadurch besser zu verstehen, was passiert.
Turingmaschine
Das 1936 von Alan Turing beschriebene Modell der Turingmaschine ist, einfach formuliert, ein theoretisches Gerät zur Simulation von Algorithmen. Im Folgenden soll es kurz vereinfacht dargestellt werden.
Aufbau
Eine Turingmaschine besteht aus einem unendlichen und in gleichgroße Felder eingeteilten Speicherband, einem entlang des Bandes beweglichen Schreib- und Lesekopf sowie einem Programm zur Steuerung des Kopfes (vgl. Abbildung 1).
Funktionsweise
Während der Ausführung eines Programms auf der Turingmaschine wird der Wert des Feldes unter dem Schreib-/Lesekopf ausgelesen und dem Programm entsprechend neu beschrieben. Dann wird der Kopf in der vom Programm vorgegeben Richtung links oder rechts entlang des Speicherbandes ein Feld weiter bewegt.
Das Programm kann dabei verschiedene Zustände einnehmen und je nach Zustand unterschiedliche Handlungen hervorrufen, auch wenn der abgelesene Wert der gleiche ist.
Jeder Schritt der Turingmaschine kann dabei unterteilt werden in:
- Feststellen, in welchem Zustand sich die Maschine gerade befindet
- Auslesen des aktuellen Feldes
Aus dem aktuellen Zustand und dem ausgelesenen Wert ergibt sich laut Programm:
- neuen Zustand setzen (kann auch der gleiche Zustand sein)
- das Feld neu beschreiben (kann auch der gleiche Wert sein)
- den Lesekopf nach links bzw. rechts bewegen oder die Maschine anhalten.
Sollte die letzte Richtungsangabe keinen Halt verursachen, wird der Zyklus für das erreichte Feld erneut durchlaufen.
Programm
Ein Programm für eine Turingmaschine lässt sich als Tabelle darstellen und soll hier am Beispiel eines Sortieralgorithmus gezeigt werden (Siehe Abbildung 2). Mit Hilfe dieses Algorithmus lässt sich eine zufällige und beliebig lange Reihe von zwei verschiedenen Zeichen (hier 0 und 1) in eine Ordnung bringen (hier von links nach rechts erst 0 dann 1). Die zu sortierende Reihe muss hierbei von leeren Feldern eingeschlossen sein, damit die Turingmaschine weiß, wo die Reihe anfängt und aufhört.
Beispiel für einen Speicherbandinhalt vor dem Durchlauf des Programmes:
1 0 0 1 1 1 0 1 0 1 0 0
Der Speicherbandinhalt nach dem Durchlauf des Programmes:
0 0 0 0 0 0 1 1 1 1 1 1