Essa linguagem é definida usando primos duplos regulares?

19

Deixei

L={anpn p, p+2 are prime}.

é regular?L

Esta questão parecia suspeita à primeira vista e eu percebi que ela está conectada à conjectura primária dupla . Meu problema é que a conjectura ainda não foi resolvida, portanto, não tenho certeza de como proceder para decidir se a linguagem é regular.

Daniil
fonte
Observe que se então é um quociente: (ou é o conjunto de prefixos de ). Em geral, para qualquer idioma unário o idioma é regular. L L = P / a P P P / a P={ap:p,p+2P}LL=P/aPPP/a
Sdcvvc
Uma variante divertida é . Isso é regular se a conjectura de primo gêmeo for falsa. L={ap:p and p+2 are prime}
Yuval Filmus

Respostas:

17

Se a conjectura de gêmeos primos for verdadeira, então , que é regular. Se a conjectura de primo gêmeo não for verdadeira, existem finitos primos gêmeos; de fato, existe um maior par de primos gêmeos . Nesse caso, , uma linguagem finita. Em qualquer um dos casos, você obtém uma linguagem comum, então acho que é seguro concluir que é uma linguagem comum ... só não saberemos qual é até que a conjectura primária gêmea seja resolvida. { p , p + 2 } L = { a n | n < p + 1 } LL=a{p,p+2}L={an|n<p+1}L

Patrick87
fonte
<andava fazendo muita lógica intuicionista> Poderia a conjectura primária dupla ser indecidível?
Gilles 'SO- stop being evil'
@ Gilles É realmente indecidível o termo correto aqui? Ou existem infinitos primos gêmeos ou não existem.
Zach Langley
@ZachLangley Não necessariamente: a conjectura primária dupla (TP) pode ser indecidível (no sentido de axiomas matemáticos independentes dos habituais) . Mas meu comentário foi uma piada (impossível de entender se você não sabe o que é a lógica intuicionista ; de fato, a partir de "TP ou não TP", podemos deduzir " é finito ou L é L = a ", então L é regular de qualquer maneira.LLL=aL
Gilles 'SO- stop be evil'
11

Sim, este idioma é regular. A conjectura de gêmeos primos não precisa ser resolvida para ver isso:

Suponha que a conjectura de primo gêmeo seja verdadeira, ou seja, para qualquer , podemos encontrar um primo p n tal que p + 2 seja primo. Então, em particular, L = { a n | n N } , pois a condição é sempre verdadeira. Este último idioma é expresso por um * e, portanto, regular.npnp+2L={an|nN}a

Suponha que a conjectura de gêmeos primos seja falsa. Então existe algum tal que existe algum primo p tal que p + 2 é primo, e para todo n > N , não existe nenhum p tal que p + 2 seja primo. Nesse caso, L = { a n | n N } , que é uma linguagem finita e, portanto, regular.Npp+2n>Npp+2L={an|nN}

Por distinção entre casos, concluímos que é regular.L

Alex ten Brink
fonte
9

É regular em ambos os casos.

  • L={an:n0}=L(a)
  • L
Janoma
fonte