Touringmaschinen Überführungsfunktionen und Beweise

Gast #3652788
Hallo,
ich muss folgende Aufgabe lösen und bin dabei kläglich zu scheitern:
Ich habe zwei Überführungsfunktionen:

1.

δ : (Z × Γ) → (Γ × {L, R, H} × Z)


2.

δ : (Z × Γ) → (Γ × {L, R} × Z)


In einem Fall kann der Lese-/Schreibkopf also bei
einem Kantenübergang seine Postion halten, in dem anderen Fall nicht.


Zeigen Sie, dass dies
keinen Unterschied macht, dass es also zu jeder TM, bei der der LSK 
seine Position halten kann,
eine äquivalente TM gibt, bei der er das nicht kann, und umgekehrt.


Kann mir jemand das erklären?

Danke
#3652806
Prost schrieb:
> In einem Fall kann der Lese-/Schreibkopf also bei
> einem Kantenübergang seine Postion halten, in dem anderen Fall nicht.

Wo hat eine Turing-Maschine Kanten? Der Begriff ist mir neu.

Bei solchen Aufgaben besteht ein Lösungsweg darin, in der restriktiven 
Konfiguration eine Maschine zu entwickeln, in der die fehlende 
Funktion/Ressource auf anderem Weg realisiert werden kann.

In diesem Fall kannst du einen Ansatz sogar höchstpersönlich 
ausprobieren: Wenn es dir verboten ist, den Raum zu verlassen, aber 
nicht stillstehen darfst, was machst du dann?

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 12 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.