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