Czy ten język jest zdefiniowany przy użyciu podwójnych liczb pierwszych regularnych?

19

Pozwolić

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

Czy regularny? $L$

To pytanie wyglądało podejrzanie na pierwszy rzut oka i zdałem sobie sprawę, że jest związane z hipotezą o podwójnej liczbie pierwszych . Mój problem polega na tym, że domysł nie został jeszcze rozwiązany, więc nie jestem pewien, jak mogę kontynuować ustalanie, że język jest prawidłowy.

— Daniil
źródło

Zauważ, że jeśli

to

jest ilorazem:

(lub jest to zestaw prefiksów

). Ogólnie rzecz biorąc, dla każdej jednoargumentowego języka

język

jest regularny.

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

Zabawnym wariantem jest

. Jest to normalne, jeśli hipoteza podwójnej liczby pierwotnej jest fałszywa.

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

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

— Yuval Filmus

17

Jeśli hipoteza podwójnej liczby pierwotnej jest prawdziwa, to , która jest regularna. Jeśli hipoteza o podwójnej liczbie pierwszych nie jest prawdziwa, wówczas istnieje wiele skończonych liczb pierwszych; w rzeczywistości istnieje największa para podwójnych liczb pierwszych . W tym przypadku , język skończony. W obu przypadkach otrzymujesz zwykły język, więc myślę, że bezpiecznie jest to wywnioskować $L = a^{*}$ $\{p, p + 2\}$ $L = \{a^{n} | n < p + 1\}$ jest językiem zwykłym ... po prostu nie będziemy wiedzieć, który to jest, dopóki nie rozwiąże się hipoteza podwójnej liczby pierwotnej. $L$

— Patrick87
źródło

<robiłem zbyt wiele intuicyjnej logiki> Czy hipoteza podwójnej liczby pierwotnej może być nierozstrzygalna?

— Gilles „SO- przestań być zły”

@Gilles Czy niezdecydowanie jest tutaj naprawdę właściwym terminem? Albo istnieje nieskończenie wiele bliźniaczych liczb pierwszych, albo ich nie ma.

— Zach Langley

@ZachLangley Niekoniecznie: hipoteza podwójnej liczby pierwotnej (TP) może być nierozstrzygalna (w sensie niezależnym od zwykłych aksjomatów matematycznych) . Ale mój komentarz był żartem (niemożliwy do uzyskania, jeśli nie wiesz, czym jest intuicyjna logika ; w rzeczywistości z „TP czy nie TP” możemy wywnioskować „

jest skończone lub

jest

”, więc

i tak jest regularne

L

$L$

L

$L$

L = a^{*}

$L=a^*$

L

$L$

— Gilles „SO- przestań być zły”

11

Tak, ten język jest regularny. Hipoteza podwójnej liczby pierwszej nie musi być rozwiązana, aby to zobaczyć:

Załóżmy, że hipoteza podwójnej liczby pierwszej jest prawdziwa, to znaczy dla dowolnego możemy znaleźć liczbę pierwszą taką, że jest liczbą pierwszą. W szczególności , ponieważ warunek jest zawsze spełniony. Ten ostatni jest język eksprymowanej przez i stąd regularne. $n$ $p \geq n$ $p+2$ $L = \{ a^n | n \in N \}$ $a^*$

$N$ $p$ $p+2$ $n > N$ $p$ $p+2$ $L = \{ a^n | n \leq N \}$

$L$

— Alex ten Brink
źródło

9

W obu przypadkach jest to normalne.

$L=\{a^n:n\geq 0\}=L(a^*)$
$L$

— Janoma
źródło