est

12

Si est régulier, cela signifie-t-il que est régulier?A2A

Ma tentative de preuve:

Oui, car la contradiction suppose que n'est pas régulier. Ensuite .AA2=AA

Comme la concaténation de deux langues non régulières n'est pas régulière, ne peut pas être régulier. Cela contredit notre hypothèse. Donc, est régulier. Donc, si est régulier, est régulier.A2AA2A

La preuve est-elle correcte?

Pouvons-nous généraliser cela à , , etc ...? Et aussi si est régulier alors n'a pas besoin d'être régulier?A3A4AA

Exemple: n'est pas régulier mais est régulier.A={12ii0}A

akshay
la source
2
La première preuve fait un énorme saut. Quelle est votre preuve que n'est pas régulier implique que n'est pas régulier? Le prouver correctement pourrait vous conduire à l'intuition pour aider à répondre au reste de la question, si c'est vrai. A 2AA2
Dave Clarke
@DaveClarke Modifié la preuve.
akshay
3
Comment réussissez-vous à épeler "Suis-je correct?" cette façon est très intrigante. Comme conseil général: lorsque des centaines de personnes lisent ce que vous avez écrit, la décence générale exige que vous prêtiez attention à la façon dont vous écrivez ... ;-)
Andrej Bauer
6
@AndrejBauer L'OP pourrait être quelqu'un qui n'est pas un locuteur natif de l'anglais et qui n'a peut-être pas encore eu l'occasion de recevoir un enseignement sur l'anglais formel. Ce n'est pas une raison pour décourager qui que ce soit, mais il pourrait être utile de les corriger.
Yuval Filmus

Réponses:

28

Prenons le théorème des quatre carrés de Lagrange . Il indique que si puis . Si est régulier, prenez sinon prenez . Quoi qu'il en soit, cela prouve l'existence d'un irrégulier tel que est régulier.B 4 = { 1 n | n 0 } B 2 A = B A = B 2 A A 2B={1n2|n0}B4={1n|n0}B2A=BA=B2AA2

Karolis Juodelė
la source
Je ne comprends pas cette preuve; pourriez-vous élaborer un peu?
G. Bach
2
Expliquant cette (belle) preuve: Nous avons que , et que . Observez que . Maintenant, si , alors en prenant nous avons un contre-exemple, et si alors en prenant nous avons un contre-exemple. B 4R E G B 4 = ( B 2 ) 2 B 2R E G A = B B 2R E G A = B 2BREGB4REGB4=(B2)2B2REGA=BB2REGA=B2
Shaull
1
Absolument magnifique.
vonbrand
3
@YuvalFilmus, en effet, mais je n'avais pas de preuve et je ne voulais laisser aucun doute. Maintenant, il me semble que j'en ai trouvé un. "Un nombre est une somme de deux carrés si et seulement si tous les facteurs premiers de la forme ont même un exposant dans la factorisation première de ." Soit la longueur de pompage. Considérez . Soit un nombre premier de la forme et la longueur que nous choisissons de pomper. Alors, a un exposant impair sur et n'est donc pas dans . 4 k + 3 n n w = ( n ! ) 2 p 4 k + 3 m w + ( p - 1 ) wn4k+3nnw=(n!)2p4k+3mpB2w+(p1)wmm=pwpB2
Karolis Juodelė
1
@ JonasKölker, d'accord.
Karolis Juodelė
8

Voici un exemple de langage non calculable tel que . Prenez n'importe quel non calculable (représenté comme un ensemble de nombres, par exemple les codes des machines de Turing qui s'arrêtent), et définissez Donc contient tous les mots autres que ceux de longueur pour un certain . Si était calculable, vous pourriez calculer : étant donné , déterminez si (c'est-à-dire zéros) est dans ou non. Puisque nous avons supposéA 2 = Σ K A = { w Σ : | w | 4 k  pour tous les  k K } . A 4 k k K A K k 0 4 k 4 k A K AAA2=ΣK

A={wΣ:|w|4k for all kK}.
A4kkKAKk04k4kAKn'est pas calculable, doit également être non calculable.A

Revendication: . Soit n'importe quel mot de longueur . Si n'est pas une puissance de , alors et le mot vide est dans , donc . Si est une puissance de alors n'est pas une puissance de . Écrivez , où . Les deux donc . w n n 4 w A A w A 2 n 4 n / 2 4 w = x y | x | = | y | = n / 2 x , y A w = x y A 2A2=Σwnn4wAAwA2n4n/24w=xy|x|=|y|=n/2x,yAw=xyA2

Yuval Filmus
la source
1
Pour les débutants, un croquis d'épreuve pour " indécidable" peut être de mise. En outre, un petit obstacle peut être que vous utilisez comme langage formel et comme ensemble de nombres (ce qui est juste, en supposant une sémantique appropriée pour , mais peut-être peu familière). Sinon, très belle idée. K KAKK
Raphael
2

Votre preuve fait encore un énorme bond (en faisant valoir que la concaténation des langues non régulières n'est pas régulière).

Si la conjecture de Goldbach est vraie, alors la réponse à la question est non: considérons le langage non régulier . Ensuite par la conjecture de Goldbach, A 2 = { 1 2 k : k > 1 } , qui est régulier.A={1p:p is a prime}A2={12k:k>1}

Cela ne résout pas entièrement la question, mais cela donne des preuves solides que la réponse est non (sinon la conjecture de Goldbach est fausse). Cependant, la réponse peut être très difficile à prouver, si c'est le seul exemple connu.

Shaull
la source
Que pouvons-nous conclure sur la question?
akshay
En supposant que la conjecture de Goldbach -si est régulière, A peut toujours être non régulière. Donc: prouver que la réponse est «oui» signifierait que la conjecture de Goldbach est fausse (peu probable). A2A
Shaull
2
En présence de "vraies" preuves, je ne pense pas que l'utilisation d'une conjecture non prouvée soit juste. Peut-être que la connexion est intéressante pour certains?
Raphael
En effet, après les réponses suivantes, c'est redondant. Cependant, vous pouvez voir un joli développement mathématique ici: une réponse basée sur une conjecture bien connue, puis une réponse connexe (en utilisant le théorème de Lagrange), qui est basée sur une idée similaire (décomposer un nombre en une somme).
Shaull
1
En fait, si vous utilisez des nombres premiers et semi-premiers, vous pouvez utiliser le théorème de Chen .
sdcvvc
2

La réclamation est fausse.

DxDyD|y|>4|x||x|>4|y|

A=ΣDA

A2=Σ    

|y|>2|x||y|>2|x|+2|y|>4|x|

A sonné.
la source
1A1kA1k1A
2

X1A={1}{12x:xN}{12x+1:1xX}

AA2=1

sdcvvc
la source
2

UNI={2u+1uU}{0,2,4,}L={aiiI}LL2={a2nnN}{annminI}

David Richerby
la source
0

Un autre exemple, à partir d'une question qui a été marquée comme doublon, est de considérer la langue non régulière . Tout nombre pair est la somme de et  , qui sont tous deux composites; tout nombre impair est la somme de et  , qui sont tous deux composites ( pour certains ). Par conséquent, , qui est régulier parce qu'il est co-fini (c'est le complément de ).{akm is composite}n8n44n13n99n9=2mm2A2={a8,a10}{akk12}{ϵ,a,aa,,a6,a7,a9,a11}

David Richerby
la source