0 Daumen
143 Aufrufe

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.

Avatar von

1 Antwort

0 Daumen

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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community