Ce langage est-il défini en utilisant des nombres premiers jumeaux réguliers?

19

Laisser

$\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}.$

est-il régulier? $L$

Cette question paraissait suspecte au premier coup d'œil et je me suis rendu compte qu'elle était liée à la conjecture principale jumelle . Mon problème est que la conjecture n'a pas encore été résolue, donc je ne sais pas comment puis-je procéder pour décider que la langue est régulière.

formal-languages automata regular-languages finite-automata Daniil
la source

Notez que si

alors

est un quotient:

(ou, c'est l'ensemble des préfixes de

). En général, pour toute langue unaire

la langue

est régulière.

P = {a^{p} : p, p + 2 \in P}

$P=\{a^p:p,p+2\in\mathbb{P}\}$

L

$L$

L = P / a^{*}

$L=P/a^{\ast}$

P

$P$

P

$P$

P / a^{*}

$P/a^{\ast}$

sdcvvc

Une variante amusante est

. Ceci est régulier si la conjecture du premier jumeau est fausse.

L = {a^{p} : p and p + 2 are prime}

$L = \{ a^p : p \text{ and } p+2 \text{ are prime} \}$

Yuval Filmus

17

Si la conjecture principale jumelle est vraie, alors , qui est régulier. Si la conjecture des nombres premiers jumeaux n'est pas vraie, alors il y a un nombre fini de nombres premiers jumeaux; en effet, il existe une plus grande paire de nombres premiers jumeaux . Dans ce cas, , un langage fini. Dans les deux cas, vous obtenez un langage régulier, donc je pense qu'il est prudent de conclure que est un langage régulier ... nous ne saurons simplement pas lequel c'est jusqu'à ce que la conjecture du premier jumeau soit résolue. $L = a^{*}$ $\{p, p + 2\}$ $L = \{a^{n} | n < p + 1\}$ $L$

Patrick87
la source

<fait trop de logique intuitionniste> La conjecture du premier jumeau pourrait-elle être indécidable?

Gilles 'SO- arrête d'être méchant'

@Gilles Indécidable est-il vraiment le bon terme ici? Soit il y a une infinité de nombres premiers jumeaux, soit il n'y en a pas.

Zach Langley

@ZachLangley Pas nécessairement: la conjecture principale jumelle (TP) pourrait être indécidable (au sens où elle est indépendante des axiomes mathématiques habituels) . Mais mon commentaire était une blague (impossible à obtenir si vous ne savez pas ce qu'est la logique intuitionniste ; en fait, de «TP ou non TP», nous pouvons déduire «

est fini ou

est

», donc

est régulier de toute façon.

L

$L$

L

$L$

L = a^{*}

$L=a^*$

L

$L$

SO 'Gilles- arrête d'être méchant'

11

Oui, cette langue est régulière. La conjecture du premier jumeau n'a pas besoin d'être résolue pour voir ceci:

Supposons que la conjecture du premier jumeau soit vraie, c'est-à-dire que pour tout , nous pouvons trouver un premier tel que soit premier. Alors en particulier, , car la condition est toujours vraie. Cette dernière langue est exprimable par et donc régulière. $n$ $p \geq n$ $p+2$ $L = \{ a^n | n \in N \}$ $a^*$

Supposons que la conjecture principale jumelle soit fausse. Il existe alors un certain tel qu'il existe un premier tel que est premier, et pour chaque , il n'existe pas de tel que soit premier. Dans ce cas, , qui est une langue finie, et donc régulière. $N$ $p$ $p+2$ $n > N$ $p$ $p+2$ $L = \{ a^n | n \leq N \}$

Par distinction de cas, nous concluons que est régulier. $L$

Alex ten Brink
la source

9

C'est régulier dans les deux cas.

S'il y a une infinité de nombres premiers jumeaux, alors . $L=\{a^n:n\geq 0\}=L(a^*)$
S'il existe un nombre fini de nombres premiers jumeaux, alors est fini, donc régulier. $L$

Janoma
la source

Ce langage est-il défini en utilisant des nombres premiers jumeaux réguliers?

Réponses: