Как доказать полученные= проверенные?

Question

Язык l Предполагается, что IFF есть два-место, предикат R ⊆ Σ * × σ * такой, что R вычислителен, и так, чтобы для всех x ∈ Σ *: x ∈ L ⇔ существует y такое, что r (x, y)

Язык полученным, IFF, есть какая-то машина, которая принимает каждую строку в L и либо отклоняет, либо петли на каждой строке не в л.

Как мы можем показать, что класс полуъясных проблем эквивалентен классу проверяемых проблем?Или они не?

Answer 1

Это очевидно, почему полученного языка проверяется ( $ W $ будет история вычислений машины на $ x $ ). Теперь мы покажем другой способ:

Пусть $ v (x, w) $ Будьте верификатора для $ l $ . Определите $ m (x) $ Как следующий алгоритм:

1. Пусть $ S $ Будьте пустой массив (из эмуляции Turging Machine)
2. для каждого $ W \ in \ sigma ^ *: $
   3. Добавить новую эмуляцию $ V (x, w) $ на $ S $ . < / li>
   4. для каждой эмуляции $ e \ in s: $
      5. вычислять один шаг для $ E $ . Если, $ E $ Принимается, то принимают.

      Этот алгоритм правильный, поскольку если $ x \ in l $ Тогда есть некоторые $ W \ in \ sigma ^ * $ с $ v (x, w)= true $ и, следовательно, алгоритм примет.

      Если алгоритм принят, то должен быть какой-то $ W \ in \ sigma ^ * $ где $ v ( x, w)= true $ и, таким образом, $ x \ in l $ по определению