Turing - Maschine

01.01.2015, 20:30

123michi19

Turing - Maschine

Meine Frage:
Hey, hey :-)

ich hätte ein paar Fragen zur Turing - Maschine.

Was habe ich bisher herausgefunden:

Die Turing-Maschine wird verwendet um die Berechenbarkeit von Problemstellungen zu beweisen / widerlegen.

Es gibt verschiedene Zustände.

Schreibweise:

(Z1,A) = (Z2,B,R) --> Soll heißen, wenn im Zustand 1 ein A steht, dann gehe in Zeile 2, schreibe ein B und gehe nach rechts.

Jetzt habe ich gerade ein Video gefunden, was mich leicht verwirrt. Angenommen ich starte bei Zustand 1 und es steht ein A; Wird dann solange weitergeprüft bis einmal ein anderer Buchstabe kommt?

Und wo gebe ich die Anweisung für den Anfang (also als Zeichen #) und Ende (%)

Meine Ideen:
Besten Dank :-)

02.01.2015, 07:03

Auf diesen Beitrag antworten »

Karlito

RE: Turing - Maschine

Zitat:

Original von 123michi19
Es gibt verschiedene Zustände.

Schreibweise:

(Z1,A) = (Z2,B,R) --> Soll heißen, wenn im Zustand 1 ein A steht, dann gehe in Zeile 2, schreibe ein B und gehe nach rechts.

Was Du hier beschreibst ist eine partielle Übergangsfunktion und keinen Zustand. Und die Schreibweise ist so:
$[latex]\delta(Z_1, A) = (Z_2, B, R)[/latex]$ , wobei das zweite Tupel beschreibt, in welchen Zustand gewechselt werden soll (NICHT Zeile, das war aber bestimmt ein Tippfehler, oder?). welches Zeichen auf die aktuelle Position geschrieben wird und welche Bewegung der Lese-/Schreib-Kopf danach ausführen soll.
Im Klartext heißt dass, dass wenn im Zustand [latex]Z_1[/latex]

ein A gelesen wird, dann wechselt der Zustand in [latex]Z_2[/latex]

, das A wird mit B überschieben und nach dem Schreiben bewegt sich der Kopf nach rechts.

Zitat:

Original von 123michi19
Jetzt habe ich gerade ein Video gefunden, was mich leicht verwirrt. Angenommen ich starte bei Zustand 1 und es steht ein A; Wird dann solange weitergeprüft bis einmal ein anderer Buchstabe kommt?

Das hängt von der "Programmierung" ab. Die Programmierung ist in diesem Fall die Menge der partiellen Übergangsfunktionen. in [latex]Z_2[/latex]

kann nun ein weiteres A auch durch X überschrieben werden oder die TM hält sogar an...

Zitat:

Original von 123michi19
Und wo gebe ich die Anweisung für den Anfang (also als Zeichen #) und Ende (%)

Man nimmt immer eine Bestimmte Anfangskonfiguration an. D.h. im Normalfall steht der LS-Kopf immer auf dem ersten Zeichen auf dem Eingabeband. Welche Zeichen Anfang und Ende sind, wird durch die Programmierung und durch die Definition der TM beschrieben. Die Definition ist ja durch ein Tupel gegeben: $[latex]M=(Q, \Sigma, \Gamma, \delta, q_0, \square, q_f)[/latex]$ (s. Wikipedia). Durch die Definition des Bandalphabetes $[latex]\Gamma[/latex]$ , des Blank-Zeichens $[latex]\square[/latex]$ und der Reaktionen als partielle Übergangsfunktion werden die Grenzen der Eingaben auf dem Band Festgelegt.

Gruß,

Karlito

Neue Frage »

Antworten »

Turing - Maschine

Verwandte Themen