Muss sie anhalten?

Question

Die Aufgabe HK 15 A4:
 

Es steht: Gebe eine Turingmaschine an, für die gilt L(T)=L. T ist (...), der in einem Endzustand anhält, falls w Element L ist.

Da steht ja nicht, dass wenn das Testwort nicht akzeptiert wird, es anhalten muss.

also wäre es auch richtig bei der Aufgabenstellung eine Turingmaschine zu schreiben, die nur anhält, wenn das Testwort existiert? (Volle punktzahl möglich?

Answer 1

Hallo uzcwi!

Ja, das ist vollkommen richtig! Die Turingmaschine muss lediglich in einem Endzustand anhalten (= akzeptierende Endkonfiguration), wenn das Wort akzeptiert wird.

Gruß,
Janine (Tutorin)

Answer 2

Technisch gesehen müsste die TM nicht anhalten, aber das ist nach Aufgabenstellung nicht so gedacht und macht Ihnen die Aufgabe auch nicht leichter. Im Normalfall ist es ganz natürlich, dass die TM immer anhält und um eine Endlosschleife einzubauen müssen Sie sich eher anstrengen.

Viele Grüße

Lukas König