semi-decidable=検証可能なことをどのように証明するか？

Question

言語Lは、Rが計算可能であるように2つの場所の述語RΣ*×σ*があると検証可能なIFFであり、そのようなすべてのx∈Σ*：x∈L4のために存在する（x、y）

言語は半決定的なIFFに、Lのすべての文字列を受け入れるいくつかのチューリングマシンがある また、L個の文字列をLにしない、またはループを拒否またはループする。

半決定的な問題のクラスが検証可能な問題のクラスと同等であることをどのように見せることができますか？または彼らは？

Answer 1

その明らかな理由はその明らかな理由（ $ w $ の $ xの計算履歴になるでしょう。 $ ）今、私たちは他の方法を見せます：

$ v（x、w）$ $ l $ の検証者になります。 $ m（x）$ の定義次のアルゴリズムとして。

1. $ s $ を空の配列（マシンエミュレーションのチューリングの）
$ w \ in \ sigma ^ *：$ ごとに
2. 3. $ v（x、w）$ v（x、w）$ の新しいエミュレーションを追加します。 $ s $ 。< / li>
   4. すべてのエミュレーションの場合 $ e \ in $
      5. $ e $ に1ステップを計算します。 $ E $ が受け入れられた場合、 accept

      このアルゴリズムは、 $ x \ in l $ の場合、 $ w \ in \ sigmaがあるためです。 ^ * $ $ v（x、w）= true $ 、したがって、アルゴリズムは受け入れます。

      アルゴリズムが受け入れられた場合、 $ w \ in \ sigma ^ * $ がある必要があります。ここで、 $ v（ x、w）= true $ 、したがって $ x \ in l $ によって定義