Classe de langues reconnaissables par les MT à bande unique à 3 états

9

Depuis un certain temps, je suis curieux de voir les machines de Turing avec exactement une bande et exactement 3 états (à savoir l'état de démarrage , l'état d'acceptation et l'état de rejetq0qacceptqreject ). Notez que j'autorise les alphabets de bande arbitraires (finis) (c'est-à-dire que l'alphabet de bande n'est pas limité pour égaler l'alphabet d'entrée).

Pour plus de commodité, appelez la classe de langues reconnaissables par ces MT C3 . J'ai plusieurs questions sur ce cours:

  1. Le C3 déjà été étudié?
  2. Le C3 connu pour être égal à d'autres classes de complexité / calculabilité d'intérêt?
  3. La classe C3 résistante aux changements de modèle? Par exemple, si les MT utilisées sont autorisées à rester en place pendant une seule transition (par opposition à toujours se déplacer vers la gauche ou vers la droite) ou si la bande est conçue pour être infinie dans les deux directions au lieu d'être juste à droite, la classe fait-elle des langues reconnaissables par les MT 1 bande à 3 états changent?
  4. Comment C3 rapporte-t-il à la classe des langues régulières, Regular ? (En particulier, est-ce que chaque langue régulière en C3 ?)

Une recherche (plutôt superficielle) n'a fait apparaître que ce poste cs.stackexchange qui est pertinent mais ne répond pas à mes questions et à ce document , que je n'ai pas lu suffisamment en détail pour être sûr qu'il concerne exactement la classe C3 plutôt que une classe similaire mais différente (l'article prétend prouver que (1) chaque langue en C3 est décidable et (2) que C3 et Regularsont des classes distinctes avec intersection non vide). Comme souligné dans les commentaires du post cs.stackexchange, ces types de MT peuvent être considérés comme des automates cellulaires très particuliers, donc peut-être que quelqu'un qui connaît la littérature sur la théorie des automates cellulaires pourrait aider.

Mikhail Rudoy
la source
1
Si vous n'avez qu'un seul état de non-terminaison et une seule bande (bande d'entrée), votre machine ne se souvient de rien de ce qu'elle a lu. Ainsi, il peut accepter ou rejeter exactement les entrées qui contiennent des symboles définis de l'alphabet d'entrée.
David G
4
La machine ne peut pas se souvenir de ce qu'elle a lu, mais elle peut réécrire ce qu'elle a lu avec autre chose. Je ne vois donc pas vraiment pourquoi la caractérisation que vous donnez serait correcte. (c'est-à-dire que je peux penser à une machine simple qui accepte et rejette 011 ; ici, le comportement n'est pas entièrement déterminé par les symboles qui sont en entrée). 01011
Mikhail Rudoy
1
Vous avez raison, mon intuition était fausse.
David G

Réponses:

7

La bête est extrêmement puissante , par exemple, nous pouvons construire un TM qui accepte chaque chaîne du formulaireM

LY={r0n1mAmn}

et rejette chaque chaîne du formulaire

LN={r0n1mAm>n}

L'idée est de transformer le premier en R puis de laisser la tête atteindre le milieu de la chaîne puis faire un zig-zag "sans état"; s'il atteint A avant R, il accepte.rRAR

Description informelle:

  • sur écrire R et se déplacer vers la droite (préparer le rejet)rR
  • sur écrivez c et déplacez-vous vers la droite (vers le centre)0c
  • sur écrivez > et déplacez-vous vers la gauche (marquez 1 , préparez-vous pour le prochain croisement de gauche à droite, et allez à gauche)1>1
  • sur écrivez < et déplacez-vous vers la droite (marquez un 0 , préparez-vous pour le prochain croisement de droite à gauche, et allez à droite)c<0
  • sur écrire > et allez à gauche (croisement de gauche à droite, préparez-vous pour la prochaine de droite à gauche)<>
  • sur écrire < et allez à droite (croisement de droite à gauche, préparez-vous pour la prochaine de gauche à droite)><
  • sur accepter, sur R rejeterAR
  • sur blanc rejeterb

Exemple:

  :r 0 0 0 1 1 A
   R:0 0 0 1 1 A
   R c:0 0 1 1 A
   R c c:0 1 1 A
   R c c c:1 1 A
   R c c:c > 1 A
   R c c <:> 1 A
   R c c < <:1 A
   R c c <:< > A
   R c c:< > > A
   R c:c > > > A
   R c <:> > > A
   ...
   R c < < < <:A ACCEPT

Cette technique en zigzag est utilisée dans la plus petite machine universelle de Turing à 2 états (elle a 18 symboles) construite par Rogozhin (Rogozhin 1996. TCS, 168 (2): 215-240)).

Une certaine attention doit être portée afin de prouver que s'arrête sur toutes les entrées (il suffit de noter qu'il rejette sur une entrée vierge et que tous les symboles non-stop "convergent" vers < ou > ce qui ne peut pas conduire à une boucle infinie).M<>

Comme l'a commenté DavidG, le langage reconnu par M est un surensemble de L Y (ie L YL ( M ) ) mais il ne contient aucune chaîne de L N (ie L ( M ) L N = ) et - comme l'a commenté MikhailRudoy - cela suffit pour prouver que L ( M ) n'est pas régulière.L(M)MLYLYL(M)LNL(M)LN=L(M)

En effet, si est régulier, alors L ( M ) { r 0 1 A } = L Y = { r 0 n 1 m A m n } serait régulier (ce qui n'est pas par une simple application du lemme de pompage); conduisant à une contradiction.L(M)L(M){r01A}=LY={r0n1mAmn}

Donc n'est pas régulier .L(M)

... Mais comme tous les super-héros a un talon d'Achille: il ne peut même pas reconnaître le régulier:C3

L={12n}

Informellement, il ne peut utiliser que le le plus à gauche . . . ( b est le symbole vide) ou la brume de droite 1 b . . . comme un crochet et "se dilater" dans l'autre sens; mais l'acceptation ou le rejet final ne peut pas être sur le symbole vierge du côté opposé, donc cela ne peut être fait que sur la partie intérieure des 1 s et à partir d'une entrée suffisamment longue, il peut être "truqué" en l'étirant d'un.b1...b1b...1

Enfin - après avoir lu l'article - je peux confirmer que la MT à un état décrite dans ce document correspond à votre classe ... (donc rien de nouveau ici :-) ... et la langue utilisée par l'auteur pour prouver qu'il contient les langues non régulières sont très similaires aux miennes.C3

Marzio De Biasi
la source
1
J'aime beaucoup la réponse (+1). Cependant, la MT décrite accepte une langue différente. Il, par exemple, accepte également les chaînes rrrrr00011AAAA, r000000r0000r0000r00011A, r00011A11111111 (après A, cela pourrait être n'importe quoi au lieu de celles) ...
David G
@DavidG: Vous avez raison! Je n'y ai pas trop réfléchi ... J'essaye de le réparer.
Marzio De Biasi
4
En fait, même si n'est pas le langage reconnu par la MT décrite, ce langage n'est certainement pas régulier: si cette TM est M , alors L ( M ) r 0 1 A = L donc une courte preuve par contradiction (si L ( M ) est régulier alors L ( M ) r 0 1 A = L sera également régulier; contradiction) peut montrer que L ( M ) n'est pas régulier.LML(M)r01A=LL(M)L(M)r01A=LL(M)
Mikhail Rudoy
3
@MikhailRudoy: oui! J'ai eu la même idée. J'ai ouvert cstheory pour modifier la réponse et j'ai vu votre commentaire. Voyons voir si je peux réécrire la réponse en tenant compte de votre commentaire ...
Marzio De Biasi
5

J'ai sous-estimé la puissance de ... en fait ce n'est pas trop loin de l' hypercomputation !C3

(Je poste ceci comme une réponse séparée pour plus de clarté)

On peut construire une machine de Turing état unique qui accepte les chaînes du formulaire:M

LY={a0n1mRm2n}

et rejette les chaînes du formulaire:

LN={a0n1mRm<2n}

L'idée et la construction sont similaires à celle de la réponse précédente: transformer le premier en A , laisser la tête atteindre le milieu de la chaîne puis faire un zig-zag "sans état", mais les transitions "implémentent" un "compteur binaire" "sur la première moitié de cette façon: sur Z (zéro), faites rebondir la tête vers la droite , et convertissez le Z en S (Un) la prochaine fois que la tête atteint le S , transformez-le en a ) et laissez la tête se déplacer à gauche; lorsque la tête atteint les ) transformer en un Z . La seconde moitié de la chaîne se comporte comme un compteur unaire.aAZZSS))Z

Les transitions sont:

  • sur écrire R et se déplacer vers la droite (préparer le rejet)rR
  • sur écrivez Z et déplacez-vous vers la droite (en vous déplaçant vers le centre, réglez le compteur binaire sur 0 ..)0Z
  • sur écrivez > et déplacez-vous vers la gauche (marquez 1 et décrémentez le compteur unaire, préparez-vous pour le prochain croisement de gauche à droite et rebondissez vers le compteur binaire)1>1
  • sur écrire < et allez à droite (croisement de droite à gauche de la seconde moitié de la chaîne, préparez-vous pour la prochaine de gauche à droite)><
  • sur écrire > et allez à gauche (croisement de gauche à droite de la seconde moitié de la chaîne, préparez-vous pour la prochaine de droite à gauche)<>
  • sur écrivez S et déplacez-vous vers la droite (transformez le chiffre en un et rebondissez vers la droite vers le compteur unaire)ZS
  • en écriture ) et se déplacer vers la gauche (effacer le chiffre et laisser la tête se déplacer vers la gauche comme un "porter", se préparer pour la prochaine de gauche à droite de la première partie)S)
  • on écrivez Z et déplacez-vous vers la droite (définissez le zéro qui provoquera le rebond, et laissez la tête se déplacer vers la droite))Z
  • sur accepter, sur R rejeterAR
  • sur blanc rejeterb

Exemple:

 :a 0 0 0 1 1 1 1 1 1 1 1 R
  A:0 0 0 1 1 1 1 1 1 1 1 R
  A Z:0 0 1 1 1 1 1 1 1 1 R
  ...
  A Z Z Z:1 1 1 1 1 1 1 1 R
  A Z Z:Z > 1 1 1 1 1 1 1 R
  A Z Z S:> 1 1 1 1 1 1 1 R
  A Z Z S <:1 1 1 1 1 1 1 R
  A Z Z S:< > 1 1 1 1 1 1 R
  A Z Z:S > > 1 1 1 1 1 1 R
  A Z:Z ) > > 1 1 1 1 1 1 R
  A Z S:) > > 1 1 1 1 1 1 R
  A Z S Z:> > 1 1 1 1 1 1 R
  ...
  A Z S:Z > > > 1 1 1 1 1 R
  ...
  A Z S S < < <:1 1 1 1 1 R
  ...
  A S:) ) > > > > 1 1 1 1 R
  ...
 :A ) ) ) > > > > > > > > R ---> ACCEPT

Une certaine attention doit être portée afin de prouver que s'arrête sur toutes les entrées (il suffit de noter qu'il rejette sur une entrée vierge et que tous les symboles non-stop s'arrêtent ( , S , Z ou < , > qui ne peuvent pas conduire à une boucle infinie) ).M(,S,Z<,>

Le langage est un sur-ensemble de L Y ( L YL ( M ) ) et il ne contient pas de chaînes de L N ( L ( M ) L N = ).L(M)LYLYL(M)LNL(M)LN=

Supposons que soit sans contexte , alors - par les propriétés de fermeture des CFL, en l'intersectant avec le langage régulier { r 0 1 A }, on produit un langage CF:L(M){r01A}

L(M){r01A}={a0n1mRm2n}=LY

Mais par une simple application du lemme d' Ogden pour CFL, nous pouvons prouver que : il suffit de choisir un assez long s L Y et de marquer tous les 0 s; au moins un zéro peut être pompé et quel que soit le nombre de 1 s dans la chaîne de pompage, la croissance exponentielle de 2 n conduit à une chaîne L Y ).LYCFLsLY01s2nLY

Donc n'est pas sans contexte .L(M)

... maintenant je me demande si c'est une autre réponse "réinventer la roue", ou si c'est un nouveau (petit) résultat.

Marzio De Biasi
la source
Eh bien, le langage ici est calculable dans une classe aussi faible que coNLOGTIME, donc il ne nécessite pas exactement d'hypercalcul. (En fait, et L N peuvent être séparés même en DLOGTIME.)LYLN
Emil Jeřábek
@ EmilJeřábek: J'ai dit "pas trop loin" ... ne pas étouffer les ambitions de cette petite classe ... :-)
Marzio De Biasi
2

Dans cette réponse, on suppose que les machines Turing ont des bandes infinies bidirectionnelles. Les revendications ne s'appliquent pas aux bandes infinies unidirectionnelles.

Permettez-moi de définir d'abord la classe de langages comme la classe de tous les langages décidables par les machines de Turing à une bande à 3 états ( C 3 a été définie comme la classe de langages reconnaissables par les machines de Turing à une bande à 3 états). J'ai introduit la classe C 3 parce que dans ma réponse originale, j'ai échangé inconsciemment les classes C 3 et C 3 (je n'ai considéré que la classe C 3 ).C3C3C3C3C3C3

Cette réponse est davantage un complément aux réponses @MarzioDeBiasi. Il a montré que les classes et C 3 ne sont pas contenues dans CFL et contiennent donc des langages assez intéressants. Cependant, comme je le montrerai dans ce post, chaque langue L en C ' 3 a la propriété que l'ensemble { 1 n ; n N{ 0 } } est soit en L ou en son complément L C . Ainsi C 3C3C3LC3{1n;nN{0}}LLCC3est également très restrictif, par exemple. il ne contient que des langues unaires triviales , { ε } , { 1 n ; n N } et { 1 n ; n N{ 0 } } . La classe C 3 contient un peu plus de langues unaires. Cependant, il considère que si L C 3 et 1 nL pour n 1 , alors 1{}{ε}{1n;nN}{1n;nN{0}}C3LC31nLn1 pour tout m n . 1mLmnUn corollaire simple est que toutes les langues régulières ne sont pas en ni en C 3 . Le langage{1}n'est pas non plus en C 3 ni en C 3 .C3C3{1}C3C3


Pour la revendication (en gras) sur , il suffit de prouver qu'une machine de Turing M à une bande avec 3 états qui arrête toujours accepte ou rejette toutes les chaînes de { 1 n ; n N{ 0 } } . Supposons qu'une chaîne de la forme 1 n , n N{ 0 } , est donnée à M . Il y a trois cas:C3M{1n;nN{0}}1nnN{0}M

1) Lorsque lit 1, il accepte ou rejette.M

2) Lorsque lit 1, il déplace la tête vers la gauche. MSi nous voulons que s'arrête sur cette entrée, il doit accepter, rejeter ou se déplacer vers la droite sur le symbole vierge. Par conséquent, il ne visite jamais la cellule à droite de la cellule initiale de la bande. Si tel était le cas, il s'exécuterait indéfiniment sur l'entrée 1.M

3) Lorsque lit 1, il déplace la tête vers la droite. MIl en résulte que , après étapes, le contenu de la bande est un nA est un symbole de l'alphabet de bande et la tête de M est le symbole de gauche vide à droite du dernier A . Si nous voulons que M s'arrête sur cette entrée, il doit accepter, rejeter ou se déplacer vers la gauche sur le symbole vierge. Comme dans le cas 2), la tête de M se rendra maintenant jamais la cellule directement à la gauche de la droite A . Si c'est le cas, alors M s'exécutera indéfiniment sur l'entrée 1.nAnAMAMMAM

Il est clair que dans les trois cas, accepte toutes les chaînes de l'ensemble { 1 n ; n N{ 0 } } ou il les rejette tous.M{1n;nN{0}}


La preuve de la réclamation (en gras) concernant suit la même ligne que ci-dessus. On prend une machine de Turing M à 3 bandes mono-bande qui accepte une chaîne 1 n pour certains n 1 . Supposons que M reçoive une entrée de 1 m pour m n . Nous devons prouver que M accepte cette entrée. Nous avons 3 cas:C3M1nn1M1mmnM

M

MM1nn1n

MmAmAMAM1nMnA1nM ne visite pas la cellule directement à gauche de la cellule initiale, car elle contient le symbole vide et si elle le lisait, elle s'exécuterait pour toujours.

M{1m;mn}

David G
la source
Tout d'abord, nulle part dans la question, il n'est dit que M doit s'arrêter sur toutes les entrées, de sorte que fausse une partie de la logique de cette réponse. Au-delà de cela, la logique dans plusieurs des cas n'a pas de sens pour moi. Par exemple, dans le cas 3, si M se déplace vers la gauche sur le blanc et sur A, alors M visitera la cellule directement à gauche du A le plus à droite (en contraste direct avec l'affirmation de la réponse.)
Mikhail Rudoy
Σ={1}k s.t. 1kL(M)L(M)={1nn>0}
@MikhailRudoy, ​​pour clarifier d'abord le cas 3: si la tête se déplace vers la gauche sur le symbole A et le symbole vide, elle se déplacera à gauche pour toujours et ne s'arrêtera pas. Si jamais (disons après 100 étapes) visite la cellule directement à gauche du A le plus à droite, alors dans le cas de l'entrée 1, il ne s'arrête jamais (dans ce cas, la cellule directement à gauche du A le plus à droite contiendra le symbole vide).
David G
@MikhailRudoy, ​​il est vrai que j'ai supposé qu'une machine de Turing devait s'arrêter. Je vais modifier la réponse pour inclure également la possibilité qu'elle s'exécute pour toujours. Le résultat est similaire.
David G
3
@MikhailRudoy: BTW le problème de hatling est décidable pour les machines de Turing à 1 état; voir Gabor T. Herman, The uniform stopping problem for generalized one-state turing machines . Le modèle qui y est décrit est un peu différent du vôtre: le TM accepte s'il se termine dans une configuration mortelle (il n'y a pas d'acceptation / rejet); mais le résultat s'applique également à votre modèle (il suffit d'arrêter la MT sur les symboles qui mènent à vos états supplémentaires d'acceptation / de rejet).
Marzio De Biasi