Wie beweisen Sie semi-entschieden= überprüfbar?

Question

Eine Sprache L ist nachweisbar IFF Es gibt ein zweiteiliges Prädikat R ⊆ σ * × σ *, so dass R berechenbar ist, und so dass für alle x ∈ σ *: x ∈ L ⇔ vorhanden ist, so dass R (x, y)

Eine Sprache ist semi-entschlossener IFF Es gibt etwas Turing-Maschine, das jede Zeichenfolge in l akzeptiert und entweder ablehnen oder Schlaufen auf jeder Saite nicht in l l.

Wie können wir zeigen, dass die Klasse der semi-entschlossenen Probleme der Klasse der überprüfbaren Probleme entspricht?Oder sind sie nicht?

Answer 1

Es ist offensichtlich, warum eine halb entsetzbare Sprache überprüfbar ist ( $ W $ wäre der Rechenhistorie der Maschine auf $ x $ ). Nun zeigen wir den anderen Weg:

$ V (x, w) $ Seien Sie ein Verifizierer für $ L $ . Definieren Sie $ m (x) $ als der folgende Algorithmus:

.
1. let $ s $ ein leeres Array (von Turing Maschinenemulationen)
2. für jeden $ w \ in \ sigma ^ *: $
   3. Fügen Sie eine neue Emulation von $ V (x, w) $ in $ s $ . < / li>
   4. Für jede Emulation $ E \ in S: $
      5. Berechnen Sie einen Schritt für $ E $ . Wenn, $ E $ akzeptiert, dann akzeptieren.

      Dieser Algorithmus ist korrekt, da, wenn $ x \ in L $ dann einige $ W \ in \ Sigma vorhanden ist ^ * $ mit $ v (x, w)= true $ und daher akzeptiert der Algorithmus.

      Wenn der Algorithmus akzeptiert wird, muss es einige $ w \ in \ sigma ^ * $ dort sein, wo $ V ( x, w)= true $ und somit $ x \ in L $ per Definition