[math-fun] Nice measure for Life patterns?
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? -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
[...] 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
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
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.
On Sun, Jun 24, 2012 at 7:37 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
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.
Yeah, by measure I mean on the set of finite programs, not on the plane. Usually for computing Chaitin's Omega number, we choose a prefix-free Turing machine (if the machine halts on a string p then it does not halt on a prefix or extension of p) and then use the Lebesgue measure where a string p has measure 2^{-|p|}. If we use arbitrary Turing machines, then the above method does not converge, but if we choose the measure 2^{-s|p|}, then it does for any s > 1 and has nice compressibility properties when s is computable.
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.
If I use this, then each bit of the resulting number tell whether a particular equivalence class of patterns halts, which I guess isn't what I was looking for. I suppose if I use the spiral measure I described, then I can find the convex hull of the pattern and check only those corner points when looking for the most distant index. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
Okay, here's a more principled thing which still lets you sum over infinite equivalence classes easily. Fix coordinates for your grid, and let the cell with coords (i,j) have measure c^(|i|+|j|), for arbitrary c<1. The measure of an arbitrary finitely-supported pattern P is just the sum of the measures of its alive cells. For any translation Q of P that is situated such that it straddles both coordinate axes, you'll need to compute the measure of Q by hand. But if Q is a translation of P contained entirely in one quadrant, then shifting Q one cell away from one axis (either horizontally or vertically) will multiply its measure by c. So the sum of the measures of all translates in that quadrant will be the measure of the axis-touching translate divided by (1-c)^2 Similarly if Q crosses one axis but not the other, you can shift it in one direction to scale by c. These geometric series give you a finite way to sum over all translations. And since the weights are invariant under reflections in the axes and diagonals, the sum of all these weights will be the same for the rotations and reflections of your original pattern, so you'll just need to multiply by 8 / #symmetries to get the total over the whole equivalence class. Is this what you were looking for? --Michael On Sun, Jun 24, 2012 at 11:35 PM, Mike Stay <metaweta@gmail.com> wrote:
On Sun, Jun 24, 2012 at 7:37 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
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.
Yeah, by measure I mean on the set of finite programs, not on the plane.
Usually for computing Chaitin's Omega number, we choose a prefix-free Turing machine (if the machine halts on a string p then it does not halt on a prefix or extension of p) and then use the Lebesgue measure where a string p has measure 2^{-|p|}.
If we use arbitrary Turing machines, then the above method does not converge, but if we choose the measure 2^{-s|p|}, then it does for any s > 1 and has nice compressibility properties when s is computable.
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.
If I use this, then each bit of the resulting number tell whether a particular equivalence class of patterns halts, which I guess isn't what I was looking for.
I suppose if I use the spiral measure I described, then I can find the convex hull of the pattern and check only those corner points when looking for the most distant index. -- 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.
I have a more easily-computable measure, which avoids those axis issues. -------- Let P be a pattern, which is the disjoint union of cells (x1, y1), (x2, y2), ..., (xn, yn). Then, we define a constant: S(P) = x1^2 + y1^2 + x2^2 + y2^2 + ... + xn^2 + yn^2. This is simply the sum of squared distances from the origin. Clearly, we have S(P disjointunion Q) = S(P) + S(Q), which is rather cute. Next, we want to handle translations. If our pattern P has centroid (x,y), and we translate it to form a pattern P' with centroid (x',y'), then the following identity holds thanks to the Huygens-Steiner theorem: S(P) - n(x^2 + y^2) = S(P') - n(x'^2 + y'^2) This gives us S(P') = S(P) + n(x'^2 + y'^2 - x^2 - y^2). -------- We now define R(P) = exp(-S(P)), so that summing over all translates of a pattern (and, indeed, all patterns) yields a finite measure. Disjoint union is now multiplicative: R(P disjointunion Q) = R(P) R(Q). And the Huygens-Steiner translation formula becomes: R(P') = R(P) exp(x^2 + y^2 - x'^2 - y'^2)^n. -------- Suppose P has a centroid (x,y). Then, we can compute the sum over all translations of P: Sigma(R(Translate[P, (i,j)])) = R(P) (LM) where L = Sum[integer i] [exp(n x^2 - n (x + i)^2)] and M = Sum[integer j] [exp(n y^2 - n (y + j)^2)] [Aside: The maths is much nicer if we integrated over all *real* translations of P instead of summing over all integer translations. Then, L = Sqrt[Pi/n] exp(n x^2) and M = Sqrt[Pi/n] exp(n y^2).] -------- Let's suppose we want to find the total value of R, summing over all Life patterns. We use the disjoint union formula: R(P disjointunion Q) = R(P) R(Q) where Q is just a single cell. Then, we have: R(P) + R(P disjointunion Q) = R(P) (1 + R(Q)) So, the total value of R is equal to the infinite product: Product[integer i, integer j] [1 + exp(-i^2-j^2)] According to Mathematica, this evaluates to: 13.229455772329303730238455403464234174634112652323001 034270847525567752900584753556103622375911163436936902 250061828936681214420033729814493443269508795000058792 023403572348671341891245501751290476764 -------- Sincerely, Adam P. Goucher
In practice, one would use a much smaller value of e, such as 1.0001. In this case, the sum over all Life patterns is: 1.278763170138119 * 10^11222 Mathematica code: Module[{k = 800}, Fold[Times, 1, Flatten[Table[1 + 1.0001^(-i^2 - j^2), {i, -k, k}, {j, -k, k}]]]] Sincerely, Adam P. Goucher ----- Original Message ----- From: "Adam P. Goucher" <apgoucher@gmx.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Monday, June 25, 2012 5:30 PM Subject: [math-fun] Very nice measure for Life patterns
I have a more easily-computable measure, which avoids those axis issues.
--------
Let P be a pattern, which is the disjoint union of cells (x1, y1), (x2, y2), ..., (xn, yn). Then, we define a constant:
S(P) = x1^2 + y1^2 + x2^2 + y2^2 + ... + xn^2 + yn^2.
This is simply the sum of squared distances from the origin. Clearly, we have S(P disjointunion Q) = S(P) + S(Q), which is rather cute.
Next, we want to handle translations. If our pattern P has centroid (x,y), and we translate it to form a pattern P' with centroid (x',y'), then the following identity holds thanks to the Huygens-Steiner theorem:
S(P) - n(x^2 + y^2) = S(P') - n(x'^2 + y'^2)
This gives us S(P') = S(P) + n(x'^2 + y'^2 - x^2 - y^2).
--------
We now define R(P) = exp(-S(P)), so that summing over all translates of a pattern (and, indeed, all patterns) yields a finite measure. Disjoint union is now multiplicative:
R(P disjointunion Q) = R(P) R(Q).
And the Huygens-Steiner translation formula becomes:
R(P') = R(P) exp(x^2 + y^2 - x'^2 - y'^2)^n.
--------
Suppose P has a centroid (x,y). Then, we can compute the sum over all translations of P:
Sigma(R(Translate[P, (i,j)])) = R(P) (LM)
where L = Sum[integer i] [exp(n x^2 - n (x + i)^2)] and M = Sum[integer j] [exp(n y^2 - n (y + j)^2)]
[Aside: The maths is much nicer if we integrated over all *real* translations of P instead of summing over all integer translations. Then, L = Sqrt[Pi/n] exp(n x^2) and M = Sqrt[Pi/n] exp(n y^2).]
--------
Let's suppose we want to find the total value of R, summing over all Life patterns. We use the disjoint union formula:
R(P disjointunion Q) = R(P) R(Q)
where Q is just a single cell. Then, we have:
R(P) + R(P disjointunion Q) = R(P) (1 + R(Q))
So, the total value of R is equal to the infinite product:
Product[integer i, integer j] [1 + exp(-i^2-j^2)]
According to Mathematica, this evaluates to:
13.229455772329303730238455403464234174634112652323001 034270847525567752900584753556103622375911163436936902 250061828936681214420033729814493443269508795000058792 023403572348671341891245501751290476764
--------
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Golly fans might like to try out Ready, a new app for exploring reaction-diffusion systems and other continuous cellular automata. Ready 0.3 has just been released and includes a number of interesting CA examples not possible with Golly: - Three-dimensional CA (see Patterns/bays_3D.vti). - Life on a 3D torus (see Patterns/life_torus.vtu). - CA on a Penrose tiling (see Patterns/penrose.vtu). Or if you're not interested in CA, there are heaps of examples of reaction-diffusion systems to explore. Screenshots and download links are at the Ready website: http://code.google.com/p/reaction-diffusion/ Feedback is welcome and best sent to this mailing list: https://groups.google.com/group/reaction-diffusion Andrew (on behalf of the Ready Bunch)
participants (5)
-
Adam P. Goucher -
Andrew Trevorrow -
Michael Kleber -
Mike Stay -
Robert Munafo