Come dimostrare semi-decidabile= verificabile?

Question

Una lingua l è verificabile IFF Se c'è un predicato a due posti r ⊆ σ * × σ * × × σ * in modo tale che R è computabile, e tale che per tutti x ∈ σ *: x ∈ l ⇔ esiste y tale che r (x, y)

Una lingua è semi-decidabile se c'è un po 'di macchina che accetta ogni stringa in l E respinge o loop su ogni stringa non in l.

Come possiamo dimostrare che la classe di problemi semi-decidabili è equivalente alla classe di problemi verificabili?O non lo sono?

Answer 1

è ovvio perché un linguaggio semi-decidabile è verificabile ( $ W $ sarebbe la cronologia del calcolo della macchina su $ x $ ). Ora, mostreremo l'altro modo:

Let $ v (x, w) $ essere un verificatore per $ l $ . Definisci $ m (x) $ come seguente algoritmo:

.
1. Let $ s $ Sii un array vuoto (di Turing Machine Emulations)
2. per ogni $ w \ in \ sigma ^ *: $
   3. Aggiungi una nuova emulazione di $ v (x, w) $ a $ s $ . < / Li >.
   4. per ogni emulazione $ e \ in s: $
      5. Computa un passo per $ e $ . Se, $ e $ accettato, quindi accetta.

      Questo algoritmo è corretto, poiché se $ x \ in l $ allora c'è una certa $ w \ in \ Sigma ^ * $ con $ v (x, w)= Vero $ e quindi l'algoritmo accetterà.

      Se l'algoritmo ha accettato, quindi ci deve essere un po 'di class class="container di matematica"> $ w \ in \ sigma ^ * $ dove $ v ( x, w)= Vero $ e quindi $ x \ in l $ per definizione