Pourquoi une machine Turing reconnaît-elle exactement une langue?

J'essaie de comprendre l'existence de langues non reconnaissables. Pour cela, j'ai besoin de savoir pourquoi une machine Turing ne reconnaît qu'une seule langue, pas plusieurs. Pourquoi est-ce?

Le langage reconnu par une machine de Turing est, par définition, l'ensemble de chaînes qu'elle accepte. Lorsqu'une entrée est donnée à la machine, elle est acceptée ou non. Toute entrée particulière sur cette machine est toujours acceptée (dans la langue) ou toujours non acceptée (pas dans la langue). Il n'y a donc aucun mécanisme par lequel une seule machine Turing pourrait même accepter plus d'une langue.

Pensez-y de cette façon: une MT est comme un ordinateur avec un logiciel chargé. Chaque logiciel fait une chose, non? Par exemple, pensez à votre ordinateur et supposez qu'il ne contient qu'un seul programme. Alors PC + "photoshop" ne fait que photoshop, alors que PC + "mine sweeper" ne balaye que les mines.

Ainsi, une machine de Turing est une créature très simple, qui à chaque exécution obtient une seule entrée et génère un oui ou un non . Sur quelles entrées il dit oui, et sur lequel il dit non - cela est défini par le "programme" du TM tel que déterminé par ses états et sa fonction de transition. Une fois ceux-ci fixés, le "programme" est fixe, et pour une entrée donnée, il n'y a qu'une seule réponse: Oui ou Non (accepter / rejeter). Cela définit exactement une seule langue = toutes les entrées qui donnent un Oui lorsqu'elles sont données à la MT.

En revanche, l' ensemble de toutes les MT équivaut à l'ensemble ordinateur + "logiciel" avec tous les programmes possibles. Maintenant, plus de langues peuvent être décidées - mais toujours, chaque MT spécifique décide (ou reconnaît) une seule langue.

Turing Machine fonctionne comme ils le font parce que nous choisissons de les définir ainsi. Nous pourrions avoir des définitions plus sophistiquées, mais la question est de savoir si cela servirait un but, si cela nous permettrait de faire plus de choses. Et, à notre connaissance, la réponse est non.

Il est très facile de créer des modèles de machines de Turing qui reconnaissent deux langues. Etant donné les langues et L 2 , nous pourrions définir une MT avec 2 types d'état acceptant: un pour L 1 et un pour L 2 . Une MT serait censée accepter L i si elle entre à un moment donné dans un état d'acceptation correspondant. Mais il reprendrait le calcul pour voir s'il peut également entrer dans l'autre type d'état acceptant. Et nous pourrions exiger qu'il s'arrête plus tard, ou peut-être pas. Vous pourriez alors construire la théorie entière sur de telles machines. Cela fonctionnerait et serait beaucoup plus compliqué que ce que nous faisons habituellement.$L_1$$L_2$$L_1$$L_2$$L_i$

Pour répondre à la déclaration de David Richerby selon laquelle " il n'y a pas de mécanisme par lequel une seule machine de Turing pourrait même accepter plus d'une langue ", c'est uniquement parce que nous choisissons de ne pas considérer de tels mécanismes. Même si vous limitez la MT au modèle très standard, vous pourriez dire que l'entrée est reconnue comme étant en langue lorsque la TM s'arrête dans un état acceptant avec un nombre impair d'étapes, et elle est en L 2 lorsque la TM accepte avec un nombre pair d'étapes. Grâce au non-déterminisme, cela n'empêcherait pas la MT de reconnaître les deux langues qui se croisent.$L_1$$L_2$

Le fait est que toutes sortes de variantes peuvent être utilisées pour faire la théorie. Des approches très différentes ont également été essayées pour modéliser ce qu'est le calcul, comme le lambda-calcul, la logique compinatoire, la théorie des fonctions récursives, etc.

Il a toujours été démontré qu'aucun d'entre eux ne fait quoi que ce soit qui ne puisse pas être fait par notre modèle simple où TM ne reconnaît qu'une seule langue. À tel point qu'il a été conjecturé qu'il fait tout ce qui peut être fait. C'est ce qu'on appelle la thèse de Church-Turing . C'est la pierre angulaire de la théorie de la calculabilité, qui, à notre connaissance, détermine quels langages sont reconnaissables ou non.

Donc, nous pourrions aussi bien utiliser un modèle simple, car un modèle complexe rendra notre vie plus difficile, sans aucun avantage réel.

Bien sûr, nous utilisons parfois d'autres modèles car ils nous permettent de mieux comprendre certains problèmes.

Je voudrais développer un point dans la réponse de Richerby:

Lorsqu'une entrée est donnée à la machine, elle est acceptée ou non.

La raison en est que la machine de Turing est déterministe: étant donné la même entrée et le même état de démarrage, elle fera toujours la même chose à chaque fois que vous l'exécuterez (soit se terminera dans le même état d'acceptation ou dans le même état de rejet, soit bouclera pour toujours ).

De plus, nous pouvons facilement prouver que chaque machine Turing reconnaît exactement une langue:

Supposons, par contradiction, qu'une machine de Turing M reconnaisse deux langages distincts L1 et L2. Puisque L1 et L2 sont distincts, il doit exister une chaîne S qui est en L1 mais pas en L2 (sans perte de généralité - ce pourrait être l'inverse mais la preuve se déroulerait de la même manière d'ici avec L1 et L2 échangés ). Exécutez maintenant M sur S. S'il accepte, alors une contradiction est atteinte car alors S serait dans L2. S'il n'accepte pas (rejette ou boucle), alors une contradiction est atteinte car S ne serait pas dans L1.

Une machine de Turing reconnaît une langue parce que c'est la définition du mot reconnaître : La langue qu'une machine Turing reconnaît est l'ensemble de toutes les chaînes / entrées pour lesquelles la machine Turing accepte.

La réponse à cela dépend de ce que vous comprenez exactement lorsque vous entendez par "machine de Turing". Tout modèle de calcul comprend trois composants (se limitant ici aux décideurs / accepteurs):

• syntaxe,
• sémantique,
• critères d'acceptation.

Pour les machines Turing, la syntaxe serait le tuple de l'ensemble d'états, des alphabets, de la fonction de transition, etc. La sémantique serait la définition d'un calcul , c'est-à-dire décrire comment appliquer la fonction de transition afin de dériver le contenu de la bande après quelques étapes. le critère d'acceptation est de dire: «lorsque cela se produit, nous nous arrêtons et le résultat est que».

Maintenant, les machines de Turing ne sont-elles que la syntaxe et la sémantique pour vous, ou incluez-vous également le critère d'acceptation? Si vous faites le premier, n'importe quelle MT peut accepter plusieurs langues en utilisant différents critères d'acceptation; vous pouvez même concevoir des critères d'acceptation qui permettent plusieurs langues acceptées (pensez aux MT à deux paramètres, par exemple). Si vous faites ce dernier, cependant, il n'y a pas de marge de manœuvre et le critère d'acceptation habituel autorise en effet exactement une langue par MT (de ce type).

La définition et l'utilisation habituelles du terme dans TCS incluent les trois composants. Cela a du sens car, en particulier, le changement du critère d'acceptation peut changer radicalement la classe d'objets que l'automate représente , nous devons donc fixer le critère afin de savoir de quoi nous parlons.

Par exemple, comparez les automates finis et les automates Büchi . La syntaxe et la sémantique sont exactement les mêmes, mais l'une accepte les mots finis tandis que l'autre accepte les mots infinis!
Essayez de comprendre ce qui se passe si vous branchez le critère d'acceptation des automates Büchi dans la définition de MT.

Maintenant, pourquoi le critère d'acceptation habituel est-il significatif? Tant que vous vous limitez au langage des chaînes finies, peu de choses changeront en ayant plusieurs langues par MT, au niveau conceptuel: nous serons toujours en mesure d'accepter le même ensemble de langues. Nous nous en tenons donc au modèle plus simple. Cela ne veut pas dire, cependant, qu'un modèle plus impliqué ne peut pas être utile pour la modélisation dans les applications - mais c'est au-delà de la portée de TCS (qui détient l'autorité territoriale).

$M_{1}$$L_{1}$$L_{2}$$L_{1} \neq L_{2}$$s_{1}$$s_{1} \in L_{1}$$s_{1} \notin L_{2}$$M_{1}$$s_{1}$$s_{1} \notin L_{2}$$M_{1}$$s_{1}$$s \in L_{2}$$s \notin L_{1}$

$M$$L$$s \in L$$M$$s$$s$$M$$s \in L$

$s \in L \iff M$$s$

$A_{TM}$

Une langue est un ensemble de chaînes. L'union de deux langues L1 et L2 n'est-elle pas un ensemble de chaînes (appelons-le L3), et en serait-il d'une autre langue? Ensuite, si la machine Turing reconnaît les deux langues, elle reconnaît L3, une seule langue.

aucune autre réponse n'indique l'existence de la ou des machines de Turing universelles telles que décrites / découvertes par Turing dans sa preuve d'arrêt. oui, une MT accepte une seule langue récursivement énumérable, mais l'UTM peut reconnaître n'importe quelle langue récursivement énumérable si elle est codée sur l'entrée avec la chaîne d'entrée. donc la question a une certaine qualité zen. Les MT acceptent à la fois une seule langue et toutes les langues codables possibles.