Comment prouver Semi-Decidable= vérifiable?

Question

Une langue l est vérifiable IFF il y a un prédicat à deux places R σ σ * × σ σ * tel que R est calculable, et tel que pour tous x ∈ σ *: x ∈ l ⇔ il existe y tellement que r (x, y)

Une langue est semi-décitable IFF il y a une machine de Turing qui accepte chaque chaîne dans L et soit rejeté ou boucles sur chaque chaîne non dans l.

Comment pouvons-nous montrer que la classe de problèmes semi-décrits équivaut à la classe de problèmes vérifiables?Ou sont-ils pas?

Answer 1

C'est évident pourquoi une langue semi-décritable est vérifiable ( $ w $ serait l'historique de calcul de la machine sur $ x $ ). Maintenant, nous allons montrer l'inverse:

let $ v (x, w) $ soit un vérificateur pour $ l $ . Définir $ m (x) $ comme algorithme suivant:

1. let $ s $ être un tableau vide (de Turing Machine émulations)
2. pour chaque $ w \ in \ sigma ^ *: $
   3. ajoutez une nouvelle émulation de $ v (x, w) $ à $ s $ . < / li>
   4. pour chaque émulation $ e \ in s: $
      5. calculez une étape pour $ E $ . Si, $ e $ accepté, puis accepter.

      Cet algorithme est correct, car si $ x \ in l $ il y a quelque chose $ w \ sigma ^ * $ avec $ v (x, w)= vrai $ et donc l'algorithme acceptera.

      Si l'algorithme accepté, il doit y avoir une partie $ w \ in \ sigma ^ * $ où $ v ( x, w)= true $ et donc $ x \ in l $ par définition