Touringmaschinen Überführungsfunktionen und Beweise

[Prost (Gast)]

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

[(prx) A. K. (prx)]

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?