Come dimostrare semi-decidabile= verificabile?
-
29-09-2020 - |
Domanda
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?
Soluzione
è 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:
- .
- Let $ s $ Sii un array vuoto (di Turing Machine Emulations)
- per ogni $ w \ in \ sigma ^ *: $
- Aggiungi una nuova emulazione di $ v (x, w) $ a $ s $ . < / Li >.
- per ogni emulazione $ e \ in s: $
- 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