GMU:My favorite things/Projekte/Erlebbare Turingmaschinen - Revision history

Max at 18:03, 10 January 2012

2012-01-10T18:03:59Z

Max at 18:00, 10 January 2012

2012-01-10T18:00:40Z

Md at 11:22, 9 November 2011

2011-11-09T11:22:15Z

@@ Line 26: / Line 26: @@
 * 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:
@@ Line 88: / Line 91: @@
 Dieses einfache Modell einer erlebbaren Turingmaschine soll im nächsten Abschnitt zu drei verschiedenen präsentierbaren Konzepten ausgearbeitet werden.

Md at 11:09, 9 November 2011

2011-11-09T11:09:53Z

← Older revision		Revision as of 11:09, 9 November 2011
Line 48:		Line 48:

	0 0 0 0 0 0 1 1 1 1 1 1		0 0 0 0 0 0 1 1 1 1 1 1



			=Idee einer erlebbaren Turingmaschine=

			Um den Interessierten das Konzept und die Funktionsweise einer Turingmaschine näher zu bringen, sollen sie selbst in die Rolle der Maschine schlüpfen. Dafür bietet sich am ehesten die Postition als Schreib-/Lesekopf an, da dort die Interaktion zwischen Programm und Speicherband stattfindet.

			Die Idee einer erlebbaren Turingmaschine konnte bereits von mehreren Personen an einem einfachen Modell ausprobiert werden. Dieses Modell soll im Folgenden beschrieben werden, die teilnehmenden Personen werden dabei als Agenten ('Handelnde') bezeichnet.

			==Aufbau==

			[[Image:Md-turing-modell-1.png\|thumb\|Abbildung 3: Modellaufbau]]

			[[Image:Md-turing-modell-programm.png\|thumb\|Abbildung 4: Programmanweisungen für den Modellaufbau]]

			In diesem einfachen Modell wird das Speicherband von einer Schnur gebildet, an der Buchstabenkärtchen (A und B, zufällig verteilt) befestigt sind. Die Agenten erhalten einen eigenen Vorrat an Buchstabenkärtchen, die sie während des Programmablaufs mit den bereits hängenden Kärtchen vertauschen können. Die Programminstruktionen liegen schriftlich vor (vgl. Abbildung 4), der aktuelle Maschinenzustand kann mit Hilfe einer Klammer an den Programminstruktionen markiert werden.

			==Programmierung==

			Auch hier wurden die Programmanweisungen ähnlich wie in Abbildung 4 angeordnet. Die Anweisungen wurden dabei schriftlich ausformuliert. Zur Verbesserung der Übersichtlichkeit wurden dabei sämtliche Aktionen weggelassen, die keine Änderung des Feldes oder Zustands bewirken.

			Beispiel für eine Anweisung:

			Ändere den Wert auf '''B'''.
			Ändere deinen Zustand auf '''5'''.
			Gehe weiter nach '''links'''.

			==Ablauf==

			[[Image:Md-turing-modell-2.png\|thumb\|Abbildung 5: Programmablauf]]

			[[Image:Md-turing-modell-3.png\|thumb\|Abbildung 6: Speicherband nach dem Durchlaufen des Programmes]]

			Die Agenten beginnen an einer beliebigen Stelle des Bandes (links vom ersten leeren Feld am Ende der Zeichenkette, sonst funktioniert das Programm nicht) im Programmzustand '''1'''. Im folgenden sehen sie jeweils in der Programmtabelle nach und handeln entsprechend der Instruktionen für den abgelesenen Wert und ihren gegenwärtigen Zustand so lange, bis das Programm einen HALT verlangt. Damit sollten sie die Buchstaben auf dem Band sortiert haben.

			==Ergebnisse==

			Alle Personen gaben nach einem erfolgreichen Durchlaufen des Programmes an, das Konzept der Turingmaschine besser verstanden zu haben als nach einer rein theoretischen Erklärung.

			Dieses einfache Modell einer erlebbaren Turingmaschine soll im nächsten Abschnitt zu drei verschiedenen präsentierbaren Konzepten ausgearbeitet werden.

Md at 11:01, 9 November 2011

2011-11-09T11:01:12Z

← Older revision		Revision as of 11:01, 9 November 2011
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.

Md: Created page with "'''Erlebbare Turingmaschinen'''
Moritz Dreßler, Oktober 2011 Vielen NichtinformatikerInnen fällt es schwer, das Konzept einer Turingmaschine nachzuvollziehen, auch oder g..."

2011-11-09T10:44:25Z

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..."

New page

'''Erlebbare Turingmaschinen'''<br/>
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