Skip to main content
added 826 characters in body
Source Link

$L$ is not context free, so has no context-free grammar describing it, but it is decidable, so there is an unrestricted grammar for it (there should also be a context-sensitive grammar, but I haven't thought too hard about that).

I can't see why this would have any bearing on number theoretic questions like the Riemann Hypothesis, or the Twin Prime Conjecture, all the $L$ requires is that you are able to count and say whether a number is prime, it gives no information about other numbers, or what numbers might be prime - at least any more than being able to say whether a number is prime or not.

If there is a grammar for $L$ that somehow has bearing on the RH or TPC, it is because it does something extra that this language doesn't need: there is a Turing Machine that decides $L$ by taking an input $a^{m}$, counts $m$ then passes $m$ to a TM that decides whether $M$ is prime, as we don't care about the running time of this machine we can use a simple, but slow method such as repeated attempts at division. As this TM exists, we can convert it into a grammar directly. Thus even though we don't know the precise grammar, we know that this language can be decided without knowledge further than being able to tell if a number is prime.

So there may be a grammar for $L$ that employs a trickier method that would have bearing on other matters, but it's not really anything to do with being able to generate $L$.

$L$ is not context free, so has no context-free grammar describing it, but it is decidable, so there is an unrestricted grammar for it (there should also be a context-sensitive grammar, but I haven't thought too hard about that).

I can't see why this would have any bearing on number theoretic questions like the Riemann Hypothesis, or the Twin Prime Conjecture, all the $L$ requires is that you are able to count and say whether a number is prime, it gives no information about other numbers, or what numbers might be prime - at least any more than being able to say whether a number is prime or not.

$L$ is not context free, so has no context-free grammar describing it, but it is decidable, so there is an unrestricted grammar for it (there should also be a context-sensitive grammar, but I haven't thought too hard about that).

I can't see why this would have any bearing on number theoretic questions like the Riemann Hypothesis, or the Twin Prime Conjecture, all the $L$ requires is that you are able to count and say whether a number is prime, it gives no information about other numbers, or what numbers might be prime - at least any more than being able to say whether a number is prime or not.

If there is a grammar for $L$ that somehow has bearing on the RH or TPC, it is because it does something extra that this language doesn't need: there is a Turing Machine that decides $L$ by taking an input $a^{m}$, counts $m$ then passes $m$ to a TM that decides whether $M$ is prime, as we don't care about the running time of this machine we can use a simple, but slow method such as repeated attempts at division. As this TM exists, we can convert it into a grammar directly. Thus even though we don't know the precise grammar, we know that this language can be decided without knowledge further than being able to tell if a number is prime.

So there may be a grammar for $L$ that employs a trickier method that would have bearing on other matters, but it's not really anything to do with being able to generate $L$.

Source Link

$L$ is not context free, so has no context-free grammar describing it, but it is decidable, so there is an unrestricted grammar for it (there should also be a context-sensitive grammar, but I haven't thought too hard about that).

I can't see why this would have any bearing on number theoretic questions like the Riemann Hypothesis, or the Twin Prime Conjecture, all the $L$ requires is that you are able to count and say whether a number is prime, it gives no information about other numbers, or what numbers might be prime - at least any more than being able to say whether a number is prime or not.