0 Daumen
444 Aufrufe

Hallo, ich verzweifle an folgender Aufgabe und habe keine Ahnung wie ich das Beweisen soll. Könnte mir bitte jemand die Lösung erklären, damit ich weitere Aufgaben verstehe? Vielen Dank schon im voraus, NixVersteh

Frage:

In unterschiedlichen Büchern finden sich unterschiedliche Definitionen zu Turingmaschinen.
Betrachten Sie eine TM, die in jedem Schritt den Lesekopf nicht nur nach links oder rechts
bewegen kann, sondern die den Lesekopf auch stehen lassen
kann. Beweisen Sie, dass diese TM äquivalent ist zu der die den Lesekopf nur nach rechts und links bewegen kann.

Avatar von

1 Antwort

0 Daumen

Wenn es zwei Übergänge

  • "Wird im Zustand \(q_1\) das Zeichen \(a\) gelesen, dann wird das Zeichen \(b\) geschrieben und in Zustand \(q_2\) übergegangen."

und

  • "Wird im Zustand \(q_2\) das Zeichen \(b\) gelesen, dann wird das Zeichen \(c\) geschrieben, in Zustand \(q_3\) übergegangen und der Lesekopf in Richtung \(r\) bewegt."

gibt, dann wird der erste ersetzt durch

  • "Wird im Zustand \(q_1\) das Zeichen \(a\) gelesen, dann wird das Zeichen \(c\) geschrieben, in Zustand \(q_3\) übergegangen und der Lesekopf in Richtung \(r\) bewegt."


Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community