2
$\begingroup$

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'.

  • 0
    Right, I meant a simple, potentially non-universal one, like you're asking about here.2012-10-02

2 Answers 2

3

Sure, there is one for prime numbers in wolfram's site: http://demonstrations.wolfram.com/PrimeGeneratingCellularAutomaton/

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

  • 1
    It seems this is the classical construction by [P. C. Fischer](http://en.wikipedia.org/wiki/Patrick_C._Fischer) : P.C. Fisher "Generation on primes by one dimentional real time iterative array" J. ACM, 12 (1965), pp. 388–39$4$2014-05-08
2

You will need to pay Wolfram if you want to study and understand his code, he is not an 'open source' sort of guy! I have questions about the rules he supplies in his book 'A New Kind of Science': I am developing a browser based automaton and his prime automaton rules do not produce the same result for me. Very probably my understanding of how to interpret his given rules is incorrect but I have emailed him about this but he has not replied yet!