Conjecture sur les automates à deux compteurs

Je voudrais prouver (ou réfuter) la conjecture suivante:

Conjecture : un automate à deux compteurs (2CA) ne peut pas décider de la langue suivante:

les représentations ternaire et binaire de n ont à la fois une longueur paire ou une longueur impaire$L = \{ n \mid$$n$$\}$

Un 2CA peut facilement vérifier si la représentation binaire a une longueur paire ou impaire (il suffit de continuer à diviser par deux et de mettre à jour un indicateur de "longueur paire" après chaque division); de la même manière, il peut vérifier si la représentation ternaire a une longueur paire ou impaire (il suffit de continuer à diviser par trois et de mettre à jour un indicateur de "longueur paire" après chaque division).

Mais pour calculer l'un d'eux, il doit détruire son entrée et ne peut pas le récupérer pour calculer l'autre; il semble donc qu'il n'y a aucun moyen de décider .$L$

Connaissez-vous une technique qui peut être utilisée pour prouver la conjecture?
Ou pouvez-vous réfuter la conjecture construisant un 2CA qui décide de $L$ ?

J'ai essayé la même approche suivie par Ibarra pour prouver qu'un 2CA ne peut pas décider $\{n^2\mid n \geq 1\}$ , mais cela ne semble pas être la bonne façon.

Remarque : pour plus de simplicité, un 2CA est équivalent à un programme avec une variable $c$ qui contient initialement l'entrée et le jeu d'instructions suivant:

• INC : ajoutez un à la variable;
• DEC : décrémenter $c$ (seulement s'il est supérieur à zéro);
• JZ $lab$ : si $c$ vaut zéro, passez à l'étiquette $lab$ sinon continuez;
• MUL $K$ : multipliez $c$ par le costant $K$ ;
• $K [, lab_0, lab_1,...,lab_{K-1}]$$c$$K$$c$$c = \lfloor c / K \rfloor$$c \bmod K$
• GOTO$lab$ : saut inconditionnel;
• HALT Accepter | Rejeter : arrêter et accepter ou arrêter et rejeter.

Par exemple, un programme pour vérifier si la représentation binaire de a une longueur paire est:$n$

   loop: JZ even   // test if n = 0
         DIV 2
         JZ odd    // test if n = 0
         DIV 2
         GOTO loop
   even: HALT Accept
    odd: HALT Reject

(nous pouvons construire un équivalent 2CA)

Donc, les gens continuent de me harceler pour poster ceci même si cela ne résout qu'une version simplifiée du problème. Bon alors :)

À la fin de cela, je mettrai une partie de ce que j'ai appris de l'article d'Ibarra et de Trân, et pourquoi cette méthode se décompose sur notre problème général, mais donne peut-être encore quelques informations utiles.

Mais d'abord, nous allons examiner le problème plus simple d'essayer de décider de l'ensemble

2 n$L = \{ 2^n \mid$ des représentations ternaire et binaire de ont à la fois une longueur paire ou une longueur impaire$2^n$$\}$

Notez comment cela a plutôt que comme dans le problème d'origine. En particulier, si le nombre d'entrée n'est pas une puissance de 2, nous voulons le rejeter plutôt que d'essayer de calculer sa longueur dans n'importe quelle base.$2^n$$n$

Cela simplifie grandement les choses: si le nombre d'origine est écrit en premiers comme , alors pour tous les sauf nous devons juste vérifier qu'ils sont tous .v i v 2$2^{v_2} 3^{v_3} 5^{v_5} 7^{v_7} ...$$v_i$$v_2$$0$

Cela nous permet de résoudre ce problème simplifié en utilisant un wrapper autour de l'ancienne méthode (par Minsky je suppose) de coder l'état d'un automate à compteurs dans les exposants de la factorisation principale de la variable unique d'un automate de multiplication / division, qui, comme indiqué dans l'OP ci-dessus, est à peu près équivalent à un automate à 2 compteurs.$k$

Tout d'abord, nous avons besoin d'un automate à compteur encapsuler. Nous utiliserons 3 compteurs, appelés , et .v 2 v 3 v $k$$v_2$$v_3$$v_5$

L'automate acceptera ssi les valeurs initiales du compteur, les représentations ternaire et binaire de ont à la fois une longueur paire ou une longueur impaire, et les deux et sont nuls. Lorsqu'il l'accepte, il remet d'abord à zéro tous ses compteurs.$2^{v_2}$$v_3$$v_5$

Voici un code pour cela, dans un format d'assemblage similaire à l'OP (je viens d'ajouter des variables aux instructions). Je ne l'ai pas testé, car je n'ai rien pour l'exécuter, mais je considère cela comme une formalité: les automates à 3 compteurs sont bien connus pour être Turing-complets, et pour pouvoir construire n'importe quelle fonction calculable de l'un de leurs Valeurs initiales.

// Check that v3 and v5 are both zero.
                JZ v3, check5
                GOTO reject
check5:         JZ v5, init3
                GOTO reject
// Decrement v2 until it is zero, constructing 2^n in the process.  If 2^n
// was even, we will then pass to even2 with 2^n in v3; If 2^n was odd, we
// will pass to odd2 with 2^n in v5.
init3:          INC v3          // Set v3 to 1 = 2^0 to start with.
even1:          // We have decremented v2 an even number of times so far.
                // 2^decremented amount is in v3.
                JZ v2, odd2
                DEC v2
dup3to5:        JZ v3, odd1
                DEC v3
                INC v5
                INC v5
                GOTO dup3to5
odd1:           // We have decremented v2 an odd number of times so far.
                // 2^decremented amount is in v5.
                JZ v2, even2
                DEC v2
dup5to3:        JZ v5, even1
                DEC v5
                INC v3
                INC v3
                GOTO dup5to3
// The second part checks the ternary length of 2^n, which starts out in v3
// or v5 according to whether the *binary* length of 2^n (i.e. n+1) was odd
// or even.
odd2:           // v3 needs to have odd ternary length to accept.
                // It is simplest to consider 0 to have even length in both
                // binary and ternary.  This works out as long as we're
                // consistent.
                JZ v3, reject
trisect3to5:    DEC v3
                DEC v3
                JZ v3, even2
                DEC v3
                INC v5
                GOTO trisect3to5
even2:          // v5 needs to have even ternary length to accept
                JZ v5, accept
trisect5to3:    DEC v5
                DEC v5
                JZ v5, odd2
                DEC v5
                INC v3
                GOTO trisect5to3
accept:         HALT Accept
reject:         HALT Reject

L'étape suivante consiste alors à ré-encoder ce qui précède dans les exposants d'un automate à variable unique. Comme le résultat est assez long, je vais juste décrire la méthode générale, mais une version complète (légèrement "optimisée" par endroits) est sur mon site.

                JZ vp, label
                DEC vp
next:           ...

devient (essentiellement diviser par p, puis faire le nettoyage pour annuler si la division n'était pas paire):

                DIV p, next, ..., newlabel.fp-1
newlabel.f1:    MUL p
                GOTO newlabel.i1
...
newlabel.fp-1:  MUL p
                INC
newlabel.ip-2:  INC
...
newlabel.i1:    INC
                GOTO label
next:           ...

INC vpdevient MUL p. Individuel JZet DECpeut d'abord être modifié sous la forme combinée. GOTO labelet HALT Rejectsont inchangés.

HALT Acceptserait inchangé, sauf que dans notre cas, nous avons encore une dernière vérification à faire: nous devons nous assurer qu'il n'y a pas de facteurs premiers dans le nombre autre que 2,3 et 5. Puisque notre automate à 3 compteurs particulier met à zéro les compteurs, il utilise quand il accepte, c'est simple: il suffit de tester que la variable finale est 1, ce qui peut être fait en sautant dans le code

                DEC     // BTW it cannot be zero before this.
                JZ accept
                HALT Reject
accept:         HALT Accept

Le code sur mon site Web a également une vérification initiale que le nombre n'est pas zéro, ce que je viens de réaliser est redondant avec les vérifications zéro v3, v5, eh bien.

Comme je l'ai mentionné, la méthode ci-dessus fonctionne pour le problème simplifié, mais elle n'a vraiment aucune chance de fonctionner pour le problème général, car: Dans le problème général, la valeur précise de chaque exposant du premier compte pour décider de sa taille générale et donc de sa longueur. a dans diverses bases. Cela signifie que:

• Nous n'avons pas de nombres premiers "gratuits" à utiliser pour les compteurs.
• Même si nous a fait avoir des nombres premiers gratuits pour les compteurs, nous n'avons pas vraiment un moyen d'extraire toutes les informations nécessaires de l'infiniment beaucoup d' autres nombres premiers dont les valeurs exposant ne importe.

Finissons donc avec une explication de l'essentiel de la méthode générale tirée du document lié ci-dessus par Ibarra et Trân ( version téléchargeable gratuitement ) pour savoir comment prouver que certains problèmes ne sont pas résolubles par un 2CA, et comment il se décompose de manière agaçante dans notre Cas.

Premièrement, ils modifient chaque 2CA en une "forme normale", dans laquelle les deux compteurs commutent en "phases" entre l'une ne faisant qu'augmenter et l'autre ne diminuant que jusqu'à ce qu'elle atteigne zéro. Le nombre d'états de cet automate normalisé joue un rôle important dans les estimations.$s$

Ensuite, ils analysent cet automate pour conclure qu'ils peuvent construire certaines séquences arithmétiques de nombres dont le comportement est lié. Pour être précis (certains d'entre eux ne sont pas énoncés comme des théorèmes, mais sont implicites dans la preuve de leurs deux principaux exemples):

1. Si un certain nombre x est accepté par l'automate, sans la taille du compteur non nul au début d'une phase jamais aller , alors il existe un entier tel que tous les nombres , sont acceptés.$v^x_i$$i$ $\leq s$$D>0$$x + n D$$n\geq 0$

2. Si un ensemble contient au moins nombres acceptés tels que pour chaque nombre il y a une phase telle que , alors on peut trouver et des entiers tels que$X$$s^2+1$$x\in X$$i$$v^x_i\leq s$$p, r\in X$$K_1,K_2$

   • Pour chaque entier , soit et sont tous deux acceptés par l'automate, soit les deux sont rejetés.$n\geq 0$$p + n K_1$$r + n K_2$

(Pensées:

• Ils nécessitent pour mais je pense que cela n'est en fait pas nécessaire. En fait, il en va de même pour leur acceptation.$x>s$$x\in X$
• La plupart de ces informations devraient également être valables pour les numéros rejetés , tant que le rejet se fait par arrêt explicite plutôt que par non-terminaison.)

Pour leurs propres exemples, ils utilisent également fréquemment le fait que n'ont pas de facteurs premiers . Pour prouver l'impossibilité, ils dérivent ensuite des contradictions en montrant que de telles séquences arithmétiques ne peuvent pas exister. > $D,K_1,K_2$$>s$

Dans notre problème, obtenir une contradiction de cela se décompose avec le deuxième cas. Si nous avons , où est suffisamment grand pour qu'aucun nombre entre et soit divisible par ou , alors il n'y aura pas non plus de puissances de 2 ou 3 entre et , ils sont donc tous deux acceptés ou rejetés. k p r 2 k 3 k p + 6 k n q + 6 k$K_1 = K_2 = 6^k$$k$$p$$r$$2^k$$3^k$$p + 6^k n$$q + 6^k n$

Le point 1 peut toujours être démontré comme impossible, car les pouvoirs de 2 et 3 se développent de plus en plus loin. Et je crois que je peux montrer le deuxième cas impossible si (j'ai envoyé l'argument @MarzioDeBiasi). Alors peut-être que quelqu'un pourrait utiliser ces informations pour restreindre davantage la forme de l'automate et finalement en tirer une contradiction.$K_1\neq K_2$