Comment savoir si une langue est reconnaissable, co-reconnaissable ou décidable?

8

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?

oméga
la source
"sans faire de preuves", je peux vous prouver quelque chose. (:
Ran G.
1
En mathématiques, un "truc" est généralement appelé "théorème", et parfois un "lemme".
Andrej Bauer
Certains modèles courants sont ceux traités par le théorème de Rice (prouvant un ensemble indécidable) et le théorème de Rice-Shapiro (prouvant un ensemble méconnaissable). Celles-ci sont particulièrement utiles pour le modèle "l'ensemble des MT (codées)M de telle sorte que, en cours d'exécution Mnous observons ce comportement "
chi

Réponses:

6

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Σ, wLcΣ.V accepts w,c. 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 wL, pourriez-vous prouver quewL?

Par exemple, considérez HALT={M,w | M 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 M,wHALT.

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 L¯. Ainsi pour voir si une langue est en co-RE, on peut demander:

Étant donné une chaîne wL, pourriez-vous prouver quewL?

Reprenant l'exemple de HALT, nous pouvons utiliser cette intuition pour montrer que HALTn'est pas co-reconnaissable. C'est parce que si je vous disais qu'une machineM 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 courirM 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 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={anbn | nN}. Étant donné une chaînewL, pourrais-je vous prouver que wL? Bien sûr, je pourrais compter le nombre deas et le nombre de bs et montrer qu'ils sont égaux, donc Lest reconnaissable. Et siwL? Je pourrais prouver qu'une chaîne n'est pas enL en montrant que ce n'est pas de la forme anbm ou qu'il y a un décalage dans le nombre de ale sable bs. Donc,Lest 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.

roctothorpe
la source
Merci pour ce lien! et merci à votre prof pour avoir fait ça! c'était super
nul le
2

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Σ,wL (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 TuringM et un mot w, décide siM se termine en entrée w ?

Évidemment, cela est reconnaissable , car il suffit de simulerM sur wjusqu'à ce qu'il se termine, et quand c'est le cas, dites OUI. Toutefois, siMne 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.

wazdra
la source
1

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

Steven
la source
Mêmes travaux pour les langues co-finies.
Raphael
De plus, un langage avec un espace de solution fini étant donné son entrée sera décidable puisque vous pouvez effectuer une recherche par force brute.
jmite
1

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.

jmite
la source
"Si l'espace de la solution est infiniment dénombrable, alors nous savons que le problème est reconnaissable." -- Pas nécessairement. Premièrement, l'espace de solution peut ne pas être effectivement énumérable (Exemple: "Existe-t-il une MT qui calcule une fonction totale et de sorte que [prédicat non trivial]?"). Deuxièmement, la décision de savoir si l'objet considéré est une solution peut être elle-même indécidable (Exemple: "Trouver une MT qui ne s'arrête pas le 77.").
Raphael
Ah, ça donne une idée. Nous savons queNP{L| L Decidable}, donc cela impliquerait que si nous pouvons montrer qu'un problème est dans NP (ou P d'ailleurs), il en découle simplement. Cela pourrait aider à le réduire.
Steven
Aussi: "Tout ce qui a un" ensemble de possibilités "fini à essayer sera décidable" - non. Le problème d'arrêt a deux réponses possibles mais est indécidable.
Raphael
@Steven Oui, mais c'est une preuve encore plus difficile. (L'ensemble auquel vous faites référence est généralement désigné par R, l'ensemble des langages récursifs (ly décidables).)
Raphael
Je suppose que je devrais clarifier. L'idée est que vous ne pouvez pas forcer le problème d'arrêt de la manière brute, par exemple, 3-SAT. Ou comment, lorsque vous exécutez quelque chose sur un PDA, vous pouvez essayer tous les chemins possibles même s'ils ne sont pas déterministes. Mais pour une MT, vous ne pouvez pas, car elle pourrait durer infiniment longtemps, donc l'ensemble des "choses à essayer", c'est-à-dire les chemins possibles à travers le programme, n'est pas fini.
jmite
0

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.

Denis
la source
Cette réponse favorise une mauvaise intuition, voir ici .
Raphael
Je ne suis pas d'accord pour dire que c'est une mauvaise intuition. Bien sûr, je n'ai pas mentionné tous les problèmes, par exemple le langage peut être présenté d'une manière excessivement compliquée comme dans votre exemple, et donc il faut d'abord le simplifier, pour arriver à son "essence". Je n'ai pas non plus mentionné le fait qu'il existe des langages indécidables "au-dessus" de l'arrêt, et "au-dessous" de l'arrêt, car je ne pense pas que cela aide l'intuition à ce niveau.
Denis