[...] Since any translation or reflection of a pattern has the same outcome as the original, I'd like to choose a measure on the set of cells such that computing the measure of all the translations and reflections of a pattern is easy.
I have addressed that problem four times (two Life programs including A019473; the polyominoes A181785, and the classifications A005646), each time in essentially the same way: by converting the pattern of interest into its "canonical form". So I define a "canonical(P)" function that takes a pattern P as its argument and whose value is another pattern P. To make canonical(P) I first need a well-ordering system for all possible (finite) Life patterns. To do this I define a function that compares two patterns P1 and P2 and returns -1, 0 or 1 according as the first "comes before", is the same as, or "comes after" P2 in that well-ordering. Then you can compute canonical(P) by generating all reflections and rotations (there are at most 8), comparing them to each other, and keep the one that is "smallest". The well-ordering should probably be defined in a way that fits how you represent patterns and how you store the bits and how you deal with sparseness. For example, if all of your starting patterns are guaranteed to fit on an 8x8 chessboard, then you could just turn that 8x8 grid into a 64-bit word and treat it as an integer. In any case you always need to "shift" your pattern as far towards the bottom-left as it will go so that the function gives the same answer for two patterns that differ only by a translation. Note that because of the flipping, rotating and/or shifting, canonical(P) is rarely equal to P, however canonical(canonical(P)) is always equal to canonical(P). Also, you might be able to make a brute-force search faster by generating your test patterns in such a way that they are more likely to be equal to their own canonical form. On 6/24/12, Mike Stay <metaweta@gmail.com> wrote:
I'd like to compute the first bits of the "halting probability" of Conway's life; since CAs don't halt, I'd like to compute the probability that it evolves to a state that's easily detectable by Golly, like all empty or a still life or cyclic. (Also, I know the number is uncomputable, but that doesn't preclude a finite computable prefix.) Since any translation or reflection of a pattern has the same outcome as the original, I'd like to choose a measure on the set of cells such that computing the measure of all the translations and reflections of a pattern is easy.
Any suggestions?
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com