Decidibilidade do idioma do prefixo

9

No meio do período, houve uma variante da seguinte pergunta:

Para um decidível, defina Mostre que não é necessariamente decidível.Pref ( L ) = { x | y  r  x y G } Pref ( L )L

Pref(L)={xy s.t. xyL}
Pref(L)

Mas se eu escolher L=Σ , acho que Pref(L) também é Σ , portanto, decidível. Também L= fornece o mesmo resultado. E como L deve ser decidido, não posso escolher o problema da parada ou algo assim.

  1. Como posso encontrar L tal, o Pref(L) não é decidível?
  2. Quais condições em tornarão decidíveis e quais as tornarão indecidíveis?Pref ( L )LPref(L)
Tocou.
fonte

Respostas:

9

Observe que, usando um quantificador existencial na frente de uma linguagem decidível, podemos obter qualquer linguagem re, ou seja, toda linguagem re é expressável como

{xΣyΣ x,yV}

onde é uma linguagem decidível. Isso inclui re linguagens indecidíveis como .V

ATM={e,x e encodes a Turing machine which accepts x}

A única diferença aqui é que aqui temos que nos separar e . O truque padrão é usar um novo símbolo para separar as duas partes (suponha que o separador pertença a ). Portanto, qualquer linguagem re incluindo as indecidíveis pode ser expressa neste formato.xyy

Para a segunda pergunta, não existe uma maneira algorítmica geral de verificar se os prefixos de uma determinada linguagem decidível são indecidíveis. Isto segue o teorema de Rice.

Kaveh
fonte
você pode dar explicitamente o que cria ? VATM
Ran G.
2
Seja uma cadeia de caracteres destinada a representar uma computação de em , verificará se é uma computação de M e em x de aceitação . yMexVyMex
Kaveh
Essa é uma boa solução!
Ran G.
3

Meta-conhecimento: você deseja encontrar uma linguagem não decidível que, no entanto, possua alguma propriedade computacional. Uma linguagem arbitrária e não decidível provavelmente não o levará muito longe. Mas um semi-decidível…


Dica mais forte: o que é uma linguagem semi-decidível? Significa que podemos enumerar as palavras: é um conjunto de palavras tal forma que exista um número inteiro n tal queun

u=f(n)

Olhe para esta equação um pouco, com a decisão e os prefixos em mente.


Intuitivamente falando, suponha que você tenha e gostaria de testar se está em P r e f ( L ) . Em geral, você não se sairá melhor do que marcar x a , x b , x a a etc. onde a , b , são as letras do alfabeto. Esta é uma função recursiva parcial que testa a associação em P r e f ( L ) . Obviamente, sabíamos que P r e f ( L )xPref(L)xaxbxaaa,b,Pref(L)Pref(L)já estava re; o que precisamos mostrar é que, às vezes, não há método alternativo. Vamos pegar um conjunto que é re e não recursivo, e seja f uma enumeração de S ( S = f ( x ) x N ).SNfSS=f(x)xN

Suponha que o alfabeto contenha três símbolos , 1 e : (se você tiver apenas dois símbolos { , } , codifique 0 como , 1 como e : como ). Se n N , deixar ˉ n ser n escrita em base de 2, utilizando os símbolos de 0 e 1 , sem que conduz 0 .01:{,}01:nNn¯n010

Vamos . Em inglês simples, pegamos os elementos de S e aderimos ao seu índice de enumeração. L é claramente decidível (verifique se existe um único :, que as seqüências de dois dígitos não contenham 0 inicial e que a sequência do primeiro dígito soletra a imagem por f do número que o segundo soletra). No entanto, decidir se algum ˉ y é um prefixo de L é equivalente a decidir se y está emL={y¯:x¯y=f(x)}SL:0fy¯Ly , o que você não pode prescindir de x, pois S não é recursivo por suposição. Formalmente, P r e f ( L ) não é decidível, porque P r e f ( L ) { 0 , 1 } : = S : não é decidível.SxSPref(L)Pref(L){0,1}:=S:

Gilles 'SO- parar de ser mau'
fonte