Como provar semi-decidível= verificável?

Question

Um idioma l é verificável se houver um predicado de dois lugares r ⊆ Σ * × σ * tal que r é computável, e tal que para todos x ∈ Σ *: x ∈ l ⇔ existe y tal quex, y)

Uma linguagem é semi-decidível IFF Há alguma máquina de Turing que aceita todas as string em L e rejeitar ou loops em cada string não em l.

Como podemos mostrar que a classe de problemas semi-decidíveis é equivalente à classe de problemas verificáveis?Ou eles não são?

Answer 1

É óbvio porque uma linguagem semi-decidível é verificável ( $ W $ seria o histórico de computação da máquina na $ x $ ). Agora, vamos mostrar a outra maneira:

Deixe $ v (x, w) $ ser um verificador para $ l $ . Definir $ m (x) $ como o seguinte algoritmo:

.
1. deixe $ s $ ser uma matriz vazia (de emulações de máquina de Turing)
2. para cada $ w \ in \ sigma ^ *: $
   3. Adicione uma nova emulação de $ v (x, w) $ para $ s $ . < / li >.
   4. para cada emulação $ e \ em s: $
      5. Compute um passo para $ e $ . Se, $ e $ aceito, então aceitar.

      Este algoritmo está correto, já que se $ x \ in l $ , então há alguma $ w \ in \ sigma ^ * $ com $ v (x, w)= verdadeiro $ e, portanto, o algoritmo aceitará.

      Se o algoritmo aceito, então deve haver alguma $ w \ in \ sigma ^ * $ onde $ v ( x, w)= verdadeiro $ e, portanto, $ x \ in l $ por definição