Touringmaschinen Überführungsfunktionen und Beweise

Prost Gast 12.05.2014 15:49 #3652788

Lesenswert?

•

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

Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden

(prx) A. K. (prx) 12.05.2014 15:58 #3652806

Lesenswert?

•

▲
▼

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 Zitieren Bearbeiten Löschen Beitrag melden

Touringmaschinen Überführungsfunktionen und Beweise

Antwort schreiben