Was sagt diese Reduktion LHS = LH über die Entscheidbarkeit von LHS aus?

Question

Frage:

Die Aufgabenstellung ist die folgende:

Das spezielle Halteproblem ist die Sprache: LHS = {code(T) ∈ {0, 1} ∗ | T angesetzt auf code(T) hält.}.

a) Was sagt diese Reduktion LHS <= LH über die Entscheidbarkeit von LHS aus?

Lösungsversuch:

Meine Frage wäre, stimmt jetzt meine Schlussfolgerung?

Meine Schlussfolgerung: Ich weiss das LH semi-entscheidbar ist. Ich würde jetzt sagen, ich kann sagen, dass LHS und mindestens Semi-entscheidbar ist. Ich kann mit dieser Reduktion jedoch nicht sagen ob entscheidbar ist.

Answer 1

Diese Reduktion legt nahe, dass das Halteproblem (LH) in eine spezielle Form gebracht werden kann, die als spezielles Halteproblem (LHS) bezeichnet wird, indem es auf die Codierung von Programmen beschränkt wird. Da das Halteproblem als unentscheidbar bekannt ist, deutet dies darauf hin, dass auch das spezielle Halteproblem unentscheidbar ist.