Comment prouver Semi-Decidable= vérifiable?
-
29-09-2020 - |
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?
La solution
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:
- let $ s $ être un tableau vide (de Turing Machine émulations)
- pour chaque $ w \ in \ sigma ^ *: $
- ajoutez une nouvelle émulation de $ v (x, w) $ à $ s $ . < / li>
- pour chaque émulation $ e \ in s: $
- 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