Hallo,
ich habe mich gefragt, ob das initiale Halteproblem als Teilmenge des (allgemeinen) Halteproblems aufgefasst werden kann und infolgedessen eine TM M gestartet mit dem leeren Wort Element der Sprache des (allgemeinen) Halteproblems ist, falls sie hält und nicht Element der Sprache des (allgemeinen) Halteproblems ist, falls sie nicht hält.
MfG
Ich würde sagen ja, weil H = \left\{ \langle M \rangle w \mid \text{TM}\;M\;\text{welche mit Eingabe}\;w\;\text{ halten} \right\} wird auch alle M kodieren welche mit \varepsilon halten, und weil \forall X \in \Sigma^* \ldotp X \varepsilon = X (= \varepsilon X) (i.e. \varepsilon ist das neutrale Element bezüglich der Konkatenation von Wörtern), würden alle M welche mit \varepsilon halten, direkt als \langle M \rangle in H enthalten sein, eben wie in H_\varepsilon auch.
infolgedessen eine TM M gestartet mit dem leeren Wort Element der Sprache des (allgemeinen) Halteproblems ist, falls sie hält und nicht Element der Sprache des (allgemeinen) Halteproblems ist, falls sie nicht hält.
Wenn für eine TM M, \langle M \rangle \in H_\varepsilon, dann ist auch \langle M \rangle \varepsilon \in H, weil H_\varepsilon \subset H, oder verstehe ich die Frage falsch?
1 „Gefällt mir“
Top, genau das wollte ich beides wissen, ich dachte mir bei beidem dasselbe, vielen Dank! 
Hmm, da muss man gehörig aufpassen wie man das jetzt genau betrachtet.
Intuitiv würde ich dem ganzen prima facie Recht geben, aber in BFS war es IIRC so, dass diese Kodierung \langle M\rangle w quasi ein Tupel darstellen sollte aus der Kodierung einer det. 1-Band-TM und w selbst. Damit wäre aber \langle M\rangle und \langle M\rangle\varepsilon was verschiedenes.
Es gilt am Schluss selbstverständlich, dass wenn \langle M\rangle \in H_\varepsilon auch \langle M\rangle\varepsilon \in H und auch umgekehrt, aber das folgt dann mehr aus den Beschreibungen der zwei Sprachen als durch irgendwelche Aussagen über Teilmengen.