Informatik: Turingmaschine, wie funktioniert das?

2 Antworten

Destranix
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Technik, Informatik
11.06.2020, 17:17

1.) Die Aufgabenstellung ist unzureichend. Darin steht nur, man solle irgendeine negative Zahl ausgeben. Ich vermute, es ist gemeint, man soll die gegebene Zahl negieren, davon ausgehend, dass diese in Zweierkomplementdarstellung gegeben ist.

2.) Das 7-Tupel besteht aus:

TM = (Q, Sigma, Gamma, delta, q0, F, Z);(Wobei ich nicht weiß, was Z sein soll... kenne das nur als 6-Tupel.)

Q := Menge der Zustände

Sigma := Eingabealpabeth

Gamma := Bandalpabeth

delta := Übergangsfunktion; (QxGamma -> QxGammax{L, R, N});

q0 := Startzustand

F := Menge der akzeptierenden Endzustände

Z := Ungenutzt.

Die Turingmaschine startet mit dem Kopf auf dem ersten zeichen der Eingabe und führt dann solange wie möglich mittels der Übergangsfunktionen Schritte aus. Dafür verwendet sie ihren derzeitigen Zustand und das zeichen, das sich gerade unter dem Kopf befindet und bildet dies auf einen neuen Zustand, ein neues Zeichen und eine Kopfbewegung ab.(L == links, R == rechts, N == keine Bewegung).

Du sollst jetzt entsprechend diese Werte und die Übergangsfunktion angeben, sodass die Turingmaschine entsprechend die gegebene Zahl invertiert und dann in einen akzeptierenden Endzustand übergeht.

EDIT:

Ich habe mich nocheinmal genauer erkundigt. Das Tupel müsste folgendermaßen aussehen:

TM = (Q, Sigma, Gamma, delta, q0, Z, F);

Z ist dabei das Zeichen für ein leeres feld der Turingmaschine. Dieses ist in Gamma enthalten.

Alle Felder ohne Eingabe sind anfangs mit diesem Wert gefüllt.