Deterministische Turingmaschinen - Versionsgeschichte

Css: /* Zweiband-Turingmaschinen */

2018-08-13T13:42:05Z

‎Zweiband-Turingmaschinen

Css am 5. August 2018 um 11:07 Uhr

2018-08-05T11:07:41Z

Css: /* Zweiband-Turingmaschinen */

2018-08-02T13:00:30Z

‎Zweiband-Turingmaschinen

Css am 2. August 2018 um 12:52 Uhr

2018-08-02T12:52:43Z

Css: /* Einführung */

2018-08-02T12:51:08Z

‎Einführung

Css am 2. August 2018 um 12:44 Uhr

2018-08-02T12:44:41Z

Css am 2. August 2018 um 12:24 Uhr

2018-08-02T12:24:48Z

Css: Die Seite wurde neu angelegt: „Wir betrachten nun ein anderes Berechnungsmodell. Wir werden am Ende sehen, wie es mit Automaten zusammenhängt. Zunächst arbeitet dieses Berechnungsmodell m…“

2018-08-02T11:56:41Z

Die Seite wurde neu angelegt: „Wir betrachten nun ein anderes Berechnungsmodell. Wir werden am Ende sehen, wie es mit Automaten zusammenhängt. Zunächst arbeitet dieses Berechnungsmodell m…“

Neue Seite

Wir betrachten nun ein anderes Berechnungsmodell. Wir werden am Ende sehen, wie es mit Automaten zusammenhängt.

Zunächst arbeitet dieses Berechnungsmodell mit einem '''Band'''. Als dieses Modell entwickelt wurde, waren Tonbänder gerade Stand der Technik, und dass man auf ihnen Daten speichern konnte, war klar. Formal betrachten wir ein nach beiden Seiten hin unendliches Band, eine Folge von Elementen aus einem Alphabet $\cal L$. Sei zum Beispiel $\cal L = \{0,1\}$, dann sähe ein Endlosband so aus:

-+---+---+---+---+---+---+---+-
... | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ...
-+---+---+---+---+---+---+---+-

← Nächstältere Version		Version vom 13. August 2018, 13:42 Uhr
Zeile 69:		Zeile 69:

	Entsprechend müssen die Tabellen der Zustände mehr Einträge bekommen.		Entsprechend müssen die Tabellen der Zustände mehr Einträge bekommen.
		+
		+	Eine interessante Frage ist nun, ob Zweiband-Turingmaschinen echt mehr können, als Einband-Turingmaschinen. Tatsächlich kann man aber jedes Zweiband-Programm in ein Einband-Programm umwandeln, das dazu äquivalent ist.

	[[Kategorie:TODO]]		[[Kategorie:TODO]]

← Nächstältere Version		Version vom 5. August 2018, 11:07 Uhr
Zeile 69:		Zeile 69:

	Entsprechend müssen die Tabellen der Zustände mehr Einträge bekommen.		Entsprechend müssen die Tabellen der Zustände mehr Einträge bekommen.
		+
		+	[[Kategorie:TODO]]

← Nächstältere Version		Version vom 2. August 2018, 13:00 Uhr
Zeile 56:		Zeile 56:

	== Zweiband-Turingmaschinen==		== Zweiband-Turingmaschinen==
−	Man kann nun	+	Man kann nun versuchen, Turingmaschinen zu verallgemeinern. Beispielsweise kann man ihnen mehrere Bänder geben, statt nur einem. Betrachten wir beispielsweise eine Turingmaschine mit zwei Bändern und zwei Köpfen:
		+
		+	↓
		+	-+---+---+---+---+---+---+-
		+	\| \| \| \| \| \| \|
		+	-+---+---+---+---+---+---+-
		+
		+	↓
		+	-+---+---+---+---+---+---+-
		+	\| \| \| \| \| \| \|
		+	-+---+---+---+---+---+---+-
		+
		+	Entsprechend müssen die Tabellen der Zustände mehr Einträge bekommen.

← Nächstältere Version		Version vom 2. August 2018, 12:52 Uhr
Zeile 54:		Zeile 54:
	(A) ---++---+---+--- (B) ---++---+---+--- (C) ---++---+---+---		(A) ---++---+---+--- (B) ---++---+---+--- (C) ---++---+---+---
	1 \|\| 1 \| R \| B 1 \|\| 1 \| R \| B 1 \|\| 1 \| L \| C		1 \|\| 1 \| R \| B 1 \|\| 1 \| R \| B 1 \|\| 1 \| L \| C
		+
		+	== Zweiband-Turingmaschinen==
		+	Man kann nun

@@ Zeile 30: / Zeile 30: @@
 || o1 | r1 | j1
-<code>n</code> ist dabei der Name des Zustandes. Die 0-Zeile wird ausgeführt, falls aktuell eine 0 gelesen wird. Die 1-Zeile wird ausgeführt, wenn eine 1 gelesen wird. <code>o</code> ist dabei jeweils 0 oder 1, das Zeichen, mit dem die aktuelle Speicherzelle überschrieben wird. <code>r</code> ist die richtung in die der Speicherkopf geshiftet wird, und ist entweder L (für links), S (für stationär) und R (für rechts). <code>j</code> ist dann jeweils der Name des Zustandes, zu dem gesprungen wird, oder E für Ende.
+<code>n</code> ist dabei der Name des Zustandes. Die 0-Zeile wird ausgeführt, falls aktuell eine 0 gelesen wird. Die 1-Zeile wird ausgeführt, wenn eine 1 gelesen wird. <code>o</code> ist dabei jeweils 0 oder 1, das Zeichen, mit dem die aktuelle Speicherzelle überschrieben wird. <code>r</code> ist die richtung in die der Speicherkopf geshiftet wird, und ist entweder L (für links), S (für stationär) und R (für rechts). <code>j</code> ist dann jeweils der Name des Zustandes, zu dem gesprungen wird, oder E für Ende. Statt E für Ende kann man auch, bei Entscheidungsproblemen, T und F für true und false benutzen, um anzugeben, dass die Maschine eine Eingabe akzeptiert, oder eben nicht.
 Zum Beispiel ist
@@ Zeile 41: / Zeile 41: @@
 Bei anderen Alphabeten werden es entsprechend mehr Zeilen in der Tabelle.
 == Beispiele ==

@@ Zeile 1: / Zeile 1: @@
 Wir betrachten nun ein anderes Berechnungsmodell. Wir werden am Ende sehen, wie es mit Automaten zusammenhängt.
 Zunächst arbeitet dieses Berechnungsmodell mit einem '''Band'''. Als dieses Modell entwickelt wurde, waren Tonbänder gerade Stand der Technik, und dass man auf ihnen Daten speichern konnte, war klar. Formal betrachten wir ein nach beiden Seiten hin unendliches Band, eine Folge von Elementen aus einem Alphabet $\cal L$. Sei zum Beispiel $\cal L = \{0,1\}$, dann sähe ein Endlosband so aus:
@@ Zeile 38: / Zeile 39: @@
 ein Zustand mit der Bezeichnung 19. Wird 0 gelesen, so wird 0 geschrieben (die aktuelle Zelle also unverändert beibehalten), der Kopf wird nach links verschoben, und es wird zum Zustand 22 gesprungen. Wird 1 gelesen, so wird 0 geschrieben, der Kopf wird nach rechts verschoben, und es wird zum Zustand 23 gesprungen.

← Nächstältere Version		Version vom 2. August 2018, 12:24 Uhr
Zeile 6:		Zeile 6:
	... \| 0 \| 0 \| 0 \| 0 \| 0 \| 0 \| 0 \| ...		... \| 0 \| 0 \| 0 \| 0 \| 0 \| 0 \| 0 \| ...
	-+---+---+---+---+---+---+---+-		-+---+---+---+---+---+---+---+-
		+
		+	Auf einem solchen Band haben wir einen '''Kopf''' (Lesekopf, Schreibkopf), der immer auf eine Stelle zeigt, und diese auslesen und überschreiben kann.
		+
		+	↓
		+	-+---+---+---+---+---+---+---+-
		+	... \| 0 \| 0 \| 0 \| 0 \| 0 \| 0 \| 0 \| ...
		+	-+---+---+---+---+---+---+---+-
		+
		+	Der Kopf hat als Operationen Bewegung nach rechts und links, auslesen, und schreiben.
		+
		+	Wie auch schon bei Automaten besteht unser Programm aus Zuständen. Ein Zustand kann folgendes tun:
		+
		+	* Aktuelle Speicherzelle auslesen
		+	* Aktuelle Speicherzelle überschreiben
		+	* Kopf verschieben
		+	* Zu einem anderen Zustand springen
		+
		+	Eine sinnvolle Notation für Zustände ist damit folgende Tabelle:
		+
		+	0 \|\| o0 \| r0 \| j0
		+	(n) ---++----+----+----
		+	1 \|\| o1 \| r1 \| j1
		+
		+	<code>n</code> ist dabei der Name des Zustandes. Die 0-Zeile wird ausgeführt, falls aktuell eine 0 gelesen wird. Die 1-Zeile wird ausgeführt, wenn eine 1 gelesen wird. <code>o</code> ist dabei jeweils 0 oder 1, das Zeichen, mit dem die aktuelle Speicherzelle überschrieben wird. <code>r</code> ist die richtung in die der Speicherkopf geshiftet wird, und ist entweder L (für links), S (für stationär) und R (für rechts). <code>j</code> ist dann jeweils der Name des Zustandes, zu dem gesprungen wird, oder E für Ende.
		+
		+	Zum Beispiel ist
		+
		+	0 \|\| 0 \| L \| 22
		+	(19) --++---+---+----
		+	1 \|\| 0 \| R \| 23
		+
		+	ein Zustand mit der Bezeichnung 19. Wird 0 gelesen, so wird 0 geschrieben (die aktuelle Zelle also unverändert beibehalten), der Kopf wird nach links verschoben, und es wird zum Zustand 22 gesprungen. Wird 1 gelesen, so wird 0 geschrieben, der Kopf wird nach rechts verschoben, und es wird zum Zustand 23 gesprungen.