¿Cómo demostrar semi-decidible= verificable?

Question

Un idioma L es verificable IFF Hay un predicado de dos planos R ⊆ σ * × σ * de tal que R es computable, y tal que para todos x σ σ *: x ∈ l ⇔ existe y tal que r (x, y)

Un idioma es semi-decidible IFF hay una máquina de Turing que acepta cada cadena en l y ya sea rechazos o bucles en cada cadena, no en l.

¿Cómo podemos demostrar que la clase de problemas semi-decidibles es equivalente a la clase de problemas verificables?¿O no son?

Answer 1

es obvio por lo que un lenguaje semi decidible es verificable ( $ w $ sería el historial de computación de la máquina en $ x $ ). Ahora, mostraremos otra forma:

Let $ V (x, w) $ Be un verificador para $ l $ . Define $ m (x) $ como el siguiente algoritmo:

1. Let $ s $ Sé una matriz vacía (de emulaciones de máquinas de Turing)
2. para cada $ w \ in \ sigma ^ *: $
   3. Agregue una nueva emulación de $ V (x, w) $ a $ s $ . < / li>
   4. por cada emulación $ e \ in s: $
      5. Calcule un paso para $ e $ . Si, $ e $ aceptado, entonces acepté.

      Este algoritmo es correcto, ya que si $ x \ en l $ entonces hay algunos $ w \ in \ sigma ^ * $ con $ v (x, w)= true $ y, por lo tanto, el algoritmo aceptará.

      Si el algoritmo aceptó, debe haber algunos $ w \ in \ sigma ^ * $ donde $ V ( x, w)= true $ y por lo tanto $ x \ en l $ por definición