Si vous avez une langue L, sans faire de preuves, existe-t-il un moyen de savoir si elle est reconnaissable ou co-reconnaissable ou décidable?

Fondamentalement, tous les conseils ou astuces qui peuvent être utilisés pour le dire. Ou peut-être les modèles communs à rechercher pour savoir de quel type il s'agit?

L est reconnaissable

Une langue $L$ est reconnaissable si et seulement s'il existe un vérificateur pour $L$, où un vérificateur est une machine de Turing qui s'arrête sur toutes les entrées et pour tous $w \in \Sigma^*$, $w \in L \leftrightarrow \exists c \in \Sigma^*. V\text{ accepts }\langle w, c\rangle$. Communément,$c$ est considéré comme un "certificat" ou une "preuve" $w$ est dans $L$ et le vérificateur $V$ vérifie si $c$ est une preuve valable de $w$ être en $L$. (Notez que cette définition est équivalente à la définition du reconnaisseur car nous pouvons construire un reconnaisseur pour une langue à partir d'un vérificateur pour cette langue). Maintenant, pour déterminer si une langue est en RE ou non, nous pouvons poser la question suivante:

Étant donné une chaîne $w \in L$, pourriez-vous prouver que$w \in L$?

Par exemple, considérez $HALT = \{\langle M, w\rangle\ |\ M\text{ is a TM that halts on }w\}$. $HALT$ est reconnaissable parce que pour vous prouver que $M$ s'arrête $w$, Je peux juste vous dire le nombre d'étapes que vous devez exécuter $M$ pour et si $M$ ne s'arrête pas après tant d'étapes, vous serez convaincu que $\langle M, w\rangle \in HALT$.

L est co-reconnaissable

De même, une langue $L$ est co-reconnaissable si et seulement si son complément est reconnaissable, ou en d'autres termes s'il existe un vérificateur pour $\overline{L}$. Ainsi pour voir si une langue est en co-RE, on peut demander:

Étant donné une chaîne $w \not\in L$, pourriez-vous prouver que$w \not\in L$?

Reprenant l'exemple de $HALT$, nous pouvons utiliser cette intuition pour montrer que $HALT$n'est pas co-reconnaissable. C'est parce que si je vous disais qu'une machine$M$ ne s'arrête pas en entrée $w$, il n'y a vraiment rien que je puisse vous dire pour vous en convaincre. je pourrais courir$M$ sur $w$ mais même si nous avons regardé $M$ courir et ne l'ont pas encore vu s'arrêter, nous ne savons pas qu'il ne s'arrêtera pas à l'avenir.

L est décidable

Enfin, une langue $L$ est décidable si les deux $L$ et $\overline{L}$sont reconnaissables. Donc, si la réponse aux deux questions ci-dessus est oui, alors la langue est décidable.

Par exemple, considérez $L = \{a^nb^n\ |\ n \in \mathbb{N}\}$. Étant donné une chaîne$w \in L$, pourrais-je vous prouver que $w \in L$? Bien sûr, je pourrais compter le nombre de$a$s et le nombre de $b$s et montrer qu'ils sont égaux, donc $L$est reconnaissable. Et si$w \not\in L$? Je pourrais prouver qu'une chaîne n'est pas en$L$ en montrant que ce n'est pas de la forme $a^nb^m$ ou qu'il y a un décalage dans le nombre de $a$le sable $b$s. Donc,$L$est co-reconnaissable. Puisqu'il est à la fois reconnaissable et co-reconnaissable,$L$ est également décidable.

Référence: Je suis TA pour un cours d'introduction à la calculabilité / complexité de mon université et mon professeur a créé ce guide animé très utile pour raisonner sur les langages réguliers, décidables et reconnaissables.

Les idées principales

Être reconnaissable signifie que vous pouvez créer un processus automatique (nous y reviendrons plus tard) qui prend un mot comme paramètre tel que

• Si le processus automatique se termine, il renvoie OUI ou NON.
• Ce processus automatique n'a pas à se terminer sur chaque entrée, mais il doit se terminer si le mot d'entrée est dans la langue.

Être co-reconnaissable signifie la langue ${w\in \Sigma^*, w\not\in L}$ (ou, en anglais, l'ensemble de tous les mots qui ne sont pas en $L$, c'est-à-dire sa complémentarité) est reconnaissable.

Être décidable signifie que vous pouvez créer un processus automatique qui prend un mot en entrée, de telle sorte que

• Le processus automatique se termine toujours
• Il répond OUI ou NON. S'il répond OUI, le mot est dans la langue, s'il répond NON, le mot n'est pas dans la langue.

Un résultat important est que $L$ est décidable si et seulement si $L$ est reconnaissable et co-reconnaissable.

L'idée pour prouver ce résultat est que vous pouvez construire un processus automatique à partir des processus que la reconnaissance et la co-reconnaissance vous donnent, en alternant les étapes des deux processus, jusqu'à ce que l'une d'entre elles vous donne la réponse OUI. L'un d'eux doit le faire, car chaque mot est ou n'est pas dans la langue)

Processus automatiques

Sans être trop formels, de nombreux types de machines ont été conçus, et fondamentalement tous ont été liés à des types de langages (ces types dépendent des outils nécessaires pour définir ces langages. Pour plus d'informations, Chomsky Hierarchy peut vous aider).

Le sens habituel du processus automatique, en ce qui concerne la décidabilité, est une machine de Turing. Vous pouvez définir une machine de Turing de telle sorte qu'elle puisse:

• Recevoir des valeurs de l'entrée
• Enregistrer les valeurs
• Lisez les valeurs qu'il a stockées
• Calcul des opérations mathématiques de base sur les valeurs
• Testez les propriétés mathématiques de base sur ces valeurs et agissez en conséquence, en bouclant éventuellement.

Fondamentalement, une machine de Turing peut faire tout ce que vous pouvez définir dans un programme, sauf qu'il s'agit d'un objet mathématique, avec une mémoire infinie et du temps à consacrer à un calcul. Il ne se termine pas toujours.

Une autre propriété importante des machines de Turing, c'est que vous pouvez décrire une machine de Turing en un seul mot (c'est le codage), et il existe une machine de Turing qui, étant donnée en entrée le codage d'une machine $M$, et un mot $w$, peut simuler le calcul de $M$ sur l'entrée $w$. Ce sera important dans un instant.

Disons simplement que les langages réguliers - qui sont (presque) le type de langage le plus simple auquel vous pouvez penser d'un point de vue mathématique - ont la propriété particulière d'être fermés sous complément. Cela signifie essentiellement que sur ces langues, les notions de reconnaissabilité et de décidabilité sont équivalentes. Cela ne tient pas lorsque vous montez dans la hiérarchie de Chomsky.

Exemple d'un langage indécidable

Nous étudierons le problème de l' arrêt . La question est, pouvons-nous construire une machine de Turing qui, étant donné l'encodage d'une autre machine de Turing$M$ et un mot $w$, décide si$M$ se termine en entrée $w$ ?

Évidemment, cela est reconnaissable , car il suffit de simuler$M$ sur $w$jusqu'à ce qu'il se termine, et quand c'est le cas, dites OUI. Toutefois, si$M$ne se termine jamais, nous ne dirons pas NON, nous reconnaissons donc ce langage, mais ne le décidons pas. Il a été prouvé que ce langage ne peut pas être décidé par une machine de Turing. Cela implique un schéma mathématique habituel: un argument diagonal, que je n'appellerais pas intuitif. Vous pouvez vérifier ce croquis de preuve pour vous y habituer.

Pour résumer

Vous ne pourrez pas, étant donné une langue, indiquer simplement si elle est décidable ou non. Aucun algorithme ne peut le faire, et prouver qu'un langage n'est pas décidable demande une certaine réflexion et peut nécessiter des connaissances sur les machines de Turing, les arguments diagonaux, etc.

Cependant, voici ma façon personnelle de traiter cette question. Habituellement, lorsque j'étudie une langue, je suppose qu'elle est décidable, à moins qu'elle ne montre une forme de référence au fonctionnement de Turing Machine. Dans ce cas, je commence à me méfier et j'essaie de définir un algorithme pour décider de la langue. Si cela ne semble pas facile, il est parfois utile de diviser le travail à la fois dans un algorithme de reconnaissance et dans un algorithme de co-reconnaissance. Si je ne peux toujours pas le faire, j'essaierais d'établir un lien entre cette langue et une autre indécidable, comme "Si je peux décider de cette langue, je peux décider du problème d'arrêt". Il s'agit d'une réduction de Turing à un problème indécidable, donc le premier problème ne peut pas être décidable. Si tout cela échoue, je peux essayer d'utiliser des arguments diagonaux, mais cela peut être un peu délicat.

Une astuce est que si la langue est finie, alors vous savez avec certitude qu'elle est décidable - car vous pouvez "coder en dur" une machine pour accepter quoi que ce soit dans cette langue. Cependant, je trouve que le moyen le plus simple est de simplement réduire d'une autre langue

Comme je l'ai mentionné dans mon commentaire ci-dessus, je trouve utile de penser à l'espace de solution du problème.

Pensez à quelque chose comme $SAT$. Nous savons que c'est décidable, car pour le tester il y a un nombre fini de solutions que nous devons essayer. S'il y a un ensemble fini de conditions à vérifier, où l'un de ces succès garantit un oui, et aucun d'entre eux ne garantit un non, alors le problème est décidable, car nous vérifions simplement les conditions successivement. Notez que cet ensemble de conditions peut être très important (comme dans le cas de problèmes NP-complets).

Considérez maintenant que l'espace de la solution est infiniment infini, et nous pouvons générer chaque solution possible en séquence, et tester chaque solution est décidable. Dans ce cas, nous savons que le problème est reconnaissable. Par exemple, un problème demandant "y a-t-il un nombre naturel tel que ..." est reconnaissable, car nous pouvons commencer à 0 et continuer d'essayer chaque nombre dans l'ordre. S'il existe une solution, nous sommes assurés de la trouver, mais il n'y a pas nécessairement de limite sur le temps qu'il faudra pour la trouver. De plus, cet algorithme ne s'arrêterait jamais si un tel entier n'existait pas, il ne prouve donc pas qu'un problème est décidable.

Vous pouvez appliquer la même technique à l'ensemble de toutes les chaînes, tous les entiers, tous les graphiques ou toute structure finie que nous pouvons énumérer. Cela ne fonctionnerait pas pour trouver un nombre réel ou un ensemble (éventuellement infini) de chaînes.

Notez cependant que certains problèmes peuvent avoir des espaces de solution infiniment innombrables et être encore décidables.

L'astuce pour voir si un langage est indécidable est de se poser la question "puis-je coder un calcul de machine de Turing utilisant ce langage"? Ou plus généralement, "cela devient-il aussi compliqué que ce qui se passe dans un calcul?". Bien sûr, parfois, ce codage est difficile, et il est utile de connaître une liste de problèmes indécidables à réduire (comme le problème de post-correspondance). Si vous ne trouvez pas une telle réduction, essayez de penser à des algorithmes pour décider de votre langue. Par exemple, le langage des listes d'entiers en ordre croissant n'est pas fini, mais il est facile de concevoir un algorithme testant si une liste est triée en ordre croissant, donc ce langage est décidable. Et pour beaucoup de langues, nous ne connaissons pas leur décidabilité, c'est donc une question difficile.