Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there a 'simple' 2 dimensional cellular automaton to generate all prime twins ?

With 'simple' I mean not too many states per cell and not so many rules. Thus a universal turing machine equivalent cellular automaton is not 'simple'.

share|cite|improve this question
Is there one that generates all primes? That would seem to be a less specialized place to start. – mjqxxxx Oct 2 '12 at 21:09
@mjqxxxx : Well there are such because of the universality of cell auto. But if there exist such simple ones is another matter. I believe the answer to that is also yes. I believe I have seen such but Im not sure. Was there an example of that in NKS ? Maybe I saw it there. – mick Oct 2 '12 at 21:16
Right, I meant a simple, potentially non-universal one, like you're asking about here. – mjqxxxx Oct 2 '12 at 21:37

Sure, there is one for prime numbers in wolfram's site:

Source Code is also available on the right side of the page.

share|cite|improve this answer
Thanks , but I have no permission to the source code. Could you give it here ? Also Im not so good with code, maybe you can explain the rule ? Like in rule 30 or such. – mick Oct 3 '12 at 12:30
@mick You can go here for the sourcecode. – Sniper Clown Oct 10 '12 at 2:12
Thanks Mahmud +1 But I do not understand the math behind it. ( Im not so good with code either ) – mick Oct 11 '12 at 11:57
I think that this is the author: you might want to contact him, perhaps he could father explain the logic. – Sonia Oct 14 '12 at 9:19
It seems this is the classical construction by P. C. Fischer : P.C. Fisher "Generation on primes by one dimentional real time iterative array" J. ACM, 12 (1965), pp. 388–394 – user148606 May 8 '14 at 16:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.