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

13

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?

Anonyme
la source
12
Je soupçonne que vous n’avez peut-être pas une idée claire de ce que nous entendons par «langue». Pouvez-vous dire ce que vous pensez être une "langue"?
Eric Lippert
Pourquoi avez-vous besoin de savoir cela? En quoi pensez-vous que cela pourrait faire une différence?
babou

Réponses:

29

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.

David Richerby
la source
6
"Par définition", c'est exactement ce que j'aurais dit.
Dave Clarke
1
@DaveClarke Bien sûr, c'est par définition. Mais cela me semble un peu court, car il dit également que nous pourrions rendre notre définition différente, de sorte qu'une MT accepterait deux langues, ou n'importe quel nombre. En fait, je ne suis pas d'accord avec la déclaration de David Richerby selon laquelle il n'y a pas de mécanisme par lequel une MT pourrait accepter deux langues: c'est seulement parce que nous choisissons de les ignorer, et nous pourrions faire autrement. Par conséquent, la question ne reçoit pas de réponse complète, à mon humble avis, si nous n'expliquons pas ce qui le justifie.
babou
2
Je pense que le problème ici est le langage utilisé pour décrire le «langage» lui-même. Une machine de Turing accepte n'importe quoi sous la forme d'une chaîne quelle que soit notre définition du langage. Le TM définit le langage par ce qu'il accepte, ce n'est pas la même chose que notre compréhension (humaine) du langage. C'est pourquoi cette réponse est bonne et est "... entièrement répondue".
David Barker
2
Je suis d'accord avec David, l'OP a probablement lu quelque part que les machines Turing n'admettent qu'une seule langue et essaie de comprendre ce que cela signifie. Étant donné que cela provenait probablement d'une source normale, nous pouvons supposer qu'ils utilisaient la définition normale du «langage» telle que définie dans la théorie du calcul, et non une autre définition. La définition peut être arbitraire, mais c'est une définition arbitraire bien comprise et acceptée.
Cort Ammon
3
Une machine Turing qui accepte deux langues est une machine Turing qui accepte une langue qui est l'union de deux langues.
Simon Richter
9

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.

A sonné.
la source
Point mineur: je ne dirais pas qu'une MT génère "oui ou non", car cela néglige la non-terminaison. Cette simplification pourrait entraîner d'autres problèmes ultérieurement.
chi
4

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.L1L2L1L2Li

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.L1L2

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.

babou
la source
Je pense que le premier paragraphe est un peu trompeur. Je suis prêt à parier que le PO ne demande pas pourquoi nous définissons les choses de cette façon, mais qu'il ne savait même pas que c'était le cas. "Nous pourrions avoir des définitions plus sophistiquées, mais la question est de savoir si cela servirait un but" donne l'impression que vous avez besoin de connaître le but d'un concept avant de pouvoir lui donner un nom - à mon avis, c'est un mauvais façon d'apprendre.
intéressant,
L'OP dit qu'il veut savoir pourquoi TM ne reconnaît qu'une seule langue pour comprendre autre chose. Je lui réponds, ils le font parce que nous les définissons de cette façon. J'ajoute, ce qui est vrai, que nous pourrions utiliser des définitions différentes, mais cela ne changerait pas la théorie. C'est une façon de lui dire que quoi qu'il recherche, le choix de la définition est sans importance et la reconnaissabilité peut être définie pour couvrir exactement les mêmes ensembles. La raison du choix de la définition est la commodité et la fécondité, et c'est pourquoi elles évoluent avec le temps, ainsi que la façon dont les concepts sont nommés ou notés.
babou
D'accord, cela a du sens. Je pense que je m'oppose principalement à l'utilisation de "sophistiqué" - cela implique qu'une définition moins simple est souhaitable.
intéressant de noter que
3

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.

Atsby
la source
2

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.

fait intéressant
la source
2
Bienvenue en informatique ! Votre réponse est (OMI) correcte, mais je ne pense pas qu'elle s'ajoute aux réponses préexistantes. Nous avons beaucoup de questions sans réponse et il serait beaucoup plus intéressant et productif de répondre à l'une d'entre elles que de répéter les réponses existantes.
David Richerby
1
Merci! En fait, je n'ai pas vu la réponse actuellement acceptée au début (ce qui je pense est bon) parce qu'elle était si courte, et je sentais que les autres réponses ne répondaient pas à la question de manière simple.
intéressant,
1

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).

Raphael
la source
0

M1L1L2L1L2s1s1L1s1L2M1s1s1L2M1s1sL2sL1

MLsLMssMsL

sLMs

ATM

user3730788
la source
Il n'est pas nécessaire de prouver qu'une MT ne reconnaît qu'une seule langue: cela découle immédiatement de la définition de «reconnaître». Compte tenu de cette définition, il n'est même pas clair ce que signifie pour une MT d'accepter plus d'une langue (comme vous le supposez dans votre première phrase) ou si une déduction d'une telle hypothèse (comme dans votre troisième phrase) est valide. La preuve par contradiction ne fonctionne que si les déductions sont étanches: ici, l'erreur pourrait être dans l'hypothèse du comportement d'une MT qui reconnaît une MT, plutôt que dans l'hypothèse qu'une telle machine existe.
David Richerby
-2

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.

Joe Cash
la source
2
Mais la machine Turing ne reconnaît pas les deux langues à moins qu'elles ne soient en fait les mêmes. Reconnaître L1 signifie qu'il n'accepte aucune chaîne en dehors de L1; reconnaître L2 signifie qu'il n'accepte rien en dehors de L2. Si L1 et L2 sont différents, il ne peut pas reconnaître les deux.
David Richerby
-3

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.

vzn
la source
4
Non. Une machine Turing universelle accepte la langue unique {M,XM accepte X} pour un certain encodage -des machines de Turing et des intrants.
David Richerby
et en quoi est-ce différent de ce qui est écrit?
vzn
2
La reconnaissance des codages des langues n'est pas la même chose que la reconnaissance des langues.
David Richerby
oui exactement comme indiqué
vzn
1
@DavidRicherby Je pense que c'est une question de perspective. On peut certainement considérer une MT universelle comme acceptant de nombreuses langues; il suffit de l'écrire comme{(m,X)m=M,} et regardez les langues de X pour chaque numéro fixe m(curry / smn). Restreindre les MT à un paramètre est universel, mais pas nécessaire.
Raphael