Allgemeines Halteproblem und Halteproblem auf leerem Band

[mathik]

Hallo,

ich soll zeigen, dass das Halteproblem auf leerem Band H_leer nicht entscheidbar ist.
Dazu wäre meine Idee zu zeigen, dass H_leer auf das allgemeine Halteproblem H reduziert werden kann, also H_leer ≤ H bzw. es gibt eine totale berechenbare Funktion f so dass gilt:
w in H_leer <=> f(w) in H

H_leer = {w | Mw hält auf leerem Band}
H = {w.x | Mw hält bei Eingabe x}
Mw = Turingmaschine zum Codewort w

f definiere ich wie folgt:
f(w) = w.ε

Es gilt jetzt:
w in H_leer <=> w hält auf leerem Band <=> w.ε ist in H <=> f(w) ist in H

H ist semientscheidbar => H_leer ist semientscheidbar => H_leer ist nicht entscheidbar

Ist dieser Beweis korrekt?
Denn ich habe in der Literatur gesehen, dass dort H ≤ H_leer gezeigt wird. Ich frage mich jedoch, wie kann das sein? H ist doch allgemeiner als H_leer? Wie kann H_leer ≤ H und H ≤ H_leer gelten?

Gruß mathik

[theoretische theorie]

nein, der beweis ist nicht korrekt.
du willst zeigen, dass h_leer nicht entscheidbar ist, dazu reicht es nicht zu zeigen, dass h_leer als spezialfall von h betrachtet werden kann.
im gegenteil, du musst zeigen, dass das nicht-entscheidbare problem h als spezialfall von h_leer betrachtet werden kann.

dann folgt aus nicht-entscheidbarkeit des spezial-falles die nicht-entscheidbarkeit des ganzen.

[volkard]

theoretische theorie schrieb:

im gegenteil, du musst zeigen, dass das nicht-entscheidbare problem h als spezialfall von h_leer betrachtet werden kann.

also indem ich sage, daß ich zu jedem automaten und jeder anfangsbelegung des bandes einen entsprechenden ersatzautomaten bauen kann, der zuerst das zunächst leere band mit der anfangsbelegung beschreibt und dann auf den startknoten des ursprungsautomaten hüpft.

[mathik]

theoretische theorie schrieb:

nein, der beweis ist nicht korrekt.
du willst zeigen, dass h_leer nicht entscheidbar ist, dazu reicht es nicht zu zeigen, dass h_leer als spezialfall von h betrachtet werden kann.
im gegenteil, du musst zeigen, dass das nicht-entscheidbare problem h als spezialfall von h_leer betrachtet werden kann.

dann folgt aus nicht-entscheidbarkeit des spezial-falles die nicht-entscheidbarkeit des ganzen.

du hast recht. aber abgesehen von dem beweis, dass H_leer nicht entscheidbar ist. Wieso kann gleichzeitig A ≤ B und B ≤ A gelten? Ist die Reduktionsrelation etwa nicht antisymmetrisch?

[SG1]

Noe, ist sie nicht. Zum Beispiel kann man alles Probleme in NP gegenseitig aufeinander reduzieren.

[Bashar]

Das duerfte auch der Grund sein, warum nicht einfach das Relationszeichen < gewaehlt wurde.

[mathik]

Bashar schrieb:

Das duerfte auch der Grund sein, warum nicht einfach das Relationszeichen < gewaehlt wurde.

naja, aber ≤ verwendet man häufig für partielle Ordnung, deswegen auch meine falsche Annahme, dass die Reduktion auch eine partielle Ordung ist...

[Bashar]

Entweder steh ich grad aufm Schlauch (was sehr gut sein kann), oder du hast oben nur fälschlich angenommen, dass es eine strikte Ordnung ist. Von total oder partiell seh ich nichts.

[Jester]

partielle Ordnung wäre antisymmetrisch: a <= b, b<=a => a=b.

Die Relation ist einfach keine Ordnungsrelation. Weder eine strikte noch eine nicht strikte.

[Bashar]

Aber nah dran Zwischen den Repräsentanten der Äquivalenzklassen besteht eine strikte Ordnung. Ich hoffe das ist jetzt keine Tautologie

[Jester]

Selbst da wäre ich nicht einhundert Prozent sicher. Bloß weil a <= b und a <= c muß noch lange nicht b<=c oder c<=b sein. Ein partielle Ordnung kriegste so aber auf jeden Fall.