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

$\endgroup$
3
  • $\begingroup$ Is there one that generates all primes? That would seem to be a less specialized place to start. $\endgroup$
    – mjqxxxx
    Oct 2 '12 at 21:09
  • $\begingroup$ @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. $\endgroup$
    – mick
    Oct 2 '12 at 21:16
  • $\begingroup$ Right, I meant a simple, potentially non-universal one, like you're asking about here. $\endgroup$
    – mjqxxxx
    Oct 2 '12 at 21:37
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – mick
    Oct 3 '12 at 12:30
  • 1
    $\begingroup$ @mick You can go here for the sourcecode. $\endgroup$ Oct 10 '12 at 2:12
  • $\begingroup$ Thanks Mahmud +1 But I do not understand the math behind it. ( Im not so good with code either ) $\endgroup$
    – mick
    Oct 11 '12 at 11:57
  • $\begingroup$ I think that this is the author: facebook.com/joebolte you might want to contact him, perhaps he could father explain the logic. $\endgroup$
    – Sonia
    Oct 14 '12 at 9:19
  • 1
    $\begingroup$ 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 $\endgroup$
    – user148606
    May 8 '14 at 16:13
2
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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