patternModerate
Is this language defined using twin primes regular?
Viewed 0 times
thisprimesregularlanguagetwinusingdefined
Problem
Let
$\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}.$
Is $L$ regular?
This question looked suspicious at the first glance and I've realized that it is connected with the twin prime conjecture. My problem is that the conjecture has not been resolved yet, so I am not sure how can I proceed with deciding that the language is regular.
$\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}.$
Is $L$ regular?
This question looked suspicious at the first glance and I've realized that it is connected with the twin prime conjecture. My problem is that the conjecture has not been resolved yet, so I am not sure how can I proceed with deciding that the language is regular.
Solution
If the twin prime conjecture is true, then $L = a^{*}$, which is regular. If the twin prime conjecture is not true, then there are finitely many twin primes; indeed, there is a largest pair of twin primes $\{p, p + 2\}$. In this case, $L = \{a^{n} | n < p + 1\}$, a finite language. In either case, you get a regular language, so I think it's safe to conclude that $L$ is a regular language... we just won't know which one it is until the twin prime conjecture is resolved.
Context
StackExchange Computer Science Q#376, answer score: 17
Revisions (0)
No revisions yet.