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.