Décidabilité de langage préfixe

Question

A la mi-mandat il y avait une variante de la question suivante:

  

Pour un décidable $ L $ define $$ \ texte {} Préf (L) = \ {x \ mid \ existe y \ texte {S.T. } Xy \ dans L \} $$   Montrer que le texte $ \ {} Préf (L) $ est pas nécessairement décidable.

Mais si je choisis $ L = \ Sigma ^ * $, alors je pense que $ \ texte {} Préf (L) $ est $ \ Sigma ^ * $, décidable ainsi. Aussi $ L = \ emptyset $ donne le même résultat. Et puisque $ L $ doit être décidable Je ne peux pas choisir le problème de l'arrêt ou tel ..

1. Comment puis-je trouver $ L $ comme le texte $ \ {} Préf (L) $ n'est pas décidable?
2. Quelles sont les conditions sur $ L $ fera texte $ \ {} Préf (L) $ de décidable, et qui va le rendre indécidable?

Answer 1

Notez que l'utilisation d'un quantificateur existentiel devant un langage décidable nous pouvons obtenir une R.E. langue, à savoir tous les R.E. la langue est exprimable comme

$$ \ {x \ in \ Sigma ^ * \ mid \ existe y \ in \ Sigma ^ * \ \ langle x, y \ rangle \ dans V \} $$

où $ V $ est une langue décidable. Ceux-ci comprennent R.E. indécidable langues comme $$ A_ {TM} = \ {\ langle e, x \ rangle \ \ mid \ texte {$ e $ code pour une machine de Turing qui accepte $ x $} \} $$.

La seule différence ici est que nous avons ici à séparer $ x $ et $ y $ nous. L'astuce standard consiste à utiliser un nouveau symbole pour séparer les deux parties (en supposant que le séparateur appartient à $ y $). Par conséquent, toute R.E. langue y compris les indécidables peut être exprimé dans ce format.

Pour la deuxième question, il n'y a aucun moyen algorithmiques général de vérifier si les préfixes d'une langue donnée décidable est indécidable. Cela résulte du théorème de Rice.

Answer 2

métaconnaissances: vous voulez trouver une langue non décidable qui a néanmoins une propriété de calcul. Un langage arbitraire non décidable est probablement pas va vous mener très loin. Mais une demi-décidable ...

---

fort indice: ce qui est une langue semi-décidable? Cela signifie que nous pouvons énumérer les mots: il est un certain ensemble de mots $ u $ tel qu'il existe un entier $ n $ tel que

$$ u = f (n) $$

Stare à cette équation un peu, avec décidabilité et préfixes à l'esprit.

---

parlant Intuitivement, supposons que vous avez un $ x $ et que vous souhaitez tester, que ce soit en $ \ mathrm {} Préf (L) $. Tu ne vas pas faire mieux en général que chèque $ x a $, $ x $ b, $ x a un $, etc., où $ a, b, \ cdots $ sont les lettres de l'alphabet. Ceci est une fonction récursive partielle qui teste l'appartenance à $ \ mathrm {} Préf (L) $. Bien sûr, nous savions que $ \ mathrm {} Préf (L) $ était R.E. déjà; ce que nous devons montrer que parfois il n'y a pas de méthode alternative. Nous allons prendre un certain ensemble $ S \ subset \ mathbb {N} $ qui est R.E. et non récursive, et nous allons $ f $ une énumération de $ S $ ($ S = {f (x) \ mid x \ in \ mathbb {N}} $).

On suppose l'alphabet contient trois symboles $ 0 $, 1 $ et $: $ (si vous avez seulement deux symboles $ \ {\ aleph, \ beth \} $, encode $ 0 $ en $ \ aleph \ aleph $, 1 $ comme $ \ aleph \ beth $ et $: $ en $ \ beth $). Si $ n \ in \ mathbb {N} $, soit $ \ bar n $ soit $ n $ écrit en base 2 en utilisant les symboles $ 0 $ et 1 $ sans 0 initial $ $.

Soit $ L = \ {\ bar y \ mathord: \ bar x \ mid y = f (x) \} $. En clair, nous prenons les éléments de $ S $ et virement de bord sur leur indice de dénombrement. $ L $ est clairement décidable (contrôle qu'il y a un seul $: $, que les deux séquences de chiffres ne contiennent pas de premier plan $ 0 $, et en ce que la première séquence de chiffres indique l'image par $ f $ du nombre que les deuxième sorts) . Pourtant, décider si une $ \ bar y $ est un préfixe de $ L $ revient à décider si $ y $ est en $ S $, que vous ne pouvez pas faire sans savoir $ x $ depuis $ S $ est pas récursive par hypothèse . Formellement, $ \ mathrm {} Préf (L) $ n'est pas décidable, parce que $ \ mathrm {} Préf (L) \ cap \ {0,1 \} ^ * \ mathord: = S \ mathord: $ n'est pas décidable.