I originally assumed that, since you said "measure", you wanted something that was additive for disjoint patterns. But your 2^{-s|p|} example doesn't have that property, so now I'm confused. If you're just looking for an arbitrary function taking patterns to real weights, then certainly you can do this: Order the cells of the grid (e.g. in a spiral, as you said), and then binary-encode any finite-support pattern P into an integer e(P) by adding 2^k if cell k is alive in P. That's a bijection between nonnegative integers and patterns, of course. So you can push the pattern-canonicalization function C on patterns forward to a function c on integers, where "c(n) = m" if m is the minimal integer that represents a pattern equivalent to n's pattern. (Equivalence here covers translations as well as rotations and reflections.) Now you can think about the bijection between nonempty patterns P and pairs of positive integer labels (a,b), where a = how many integers <= e(P) have the same canonical pattern as P, and b = how many integers <= c(e(P)) are their own canonical pattern. That is, (a,b) means "Take the b'th canonical pattern, and then take the a'th smallest pattern equivalent to it". Then if you give label (a,b) weight 2^(-a-b), you end up with the entire equivalence class having weight 2^-b, and all patterns together having total weight 1. Well, except we left out the empty pattern, which we can relegate to weight 0. But this is all very longwinded for a not-very-interesting idea which I'm sure isn't what you were looking for anyway. It must be time for me to stop. --Michael On Sun, Jun 24, 2012 at 7:26 PM, Mike Stay <metaweta@gmail.com> wrote:
My problem isn't enumerating the patterns; I'm familiar with the notion of a canonical pattern. My problem is how to compute the measure of a pattern easily. Suppose I use the same measure I described to Warren, where we start at some arbitrary origin and then number the cells outward in a spiral. We pick some computable s > 1. Then we assign to each pattern p with a finite number of "on" cells the measure 2^{-s|p|}, where |p| is the largest index of an "on" cell. How do I compute the measure of that same pattern shifted to the right n cells, or reflected about some axis? In this case it depends greatly on the pattern.
I was hoping there is a measure on such patterns that would allow me to easily compute the measure of the whole equivalence class given just the normal form.
On Sun, Jun 24, 2012 at 2:42 PM, Robert Munafo <mrob27@gmail.com> wrote:
[...] 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.