I've had a lot of trouble grasping what you're getting at too. I get the part about "compute approximately how many patterns have a simple outcome", but am totally lost on this "measure" thing. So let's back up a bit. The "measure" seems to be a function that takes a pattern as an argument and returns something. Does it matter if the "measure" is into or onto? Same question for its inverse? It seems that the value of the "measure" function is a scalar, real-valued quantity: or is it an integer, or some kind of vector? On 6/24/12, Mike Stay <metaweta@gmail.com> wrote:
On Sun, Jun 24, 2012 at 5:08 PM, Warren Smith <warren.wds@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?
I forgot to say that I'm considering only finitely many "on" cells in the initial pattern (and therefore in its descendants). For example, number the cells starting from some arbitrary origin outwards in a spiral, let s be some computable real number greater than 1, and let the measure of a pattern p be 2^{-s|p|} where |p| is the largest index of an "on" cell in the initial pattern. Since there are nonempty finite patterns that evolve into empty ones, the measure is nonzero.
Yes, it will depend on s. If I leave s as a free parameter, it will be a thermodynamic partition function (s is the "inverse temperature" and |p| is the "energy" of p), which I think is very beautiful. Also, since Life is universal, whenever s is computable, the resulting value of the partition function will be compressible by a factor of exactly s.
My question is what the nicest measure is. I would like to generate only canonical patterns, run the pattern far enough to figure out what the end state is, and then compute the measure of all translations and reflections of the pattern. This clearly depends on the measure chosen; I want a measure that makes the measure of the translation/rotation equivalence class easy to compute.
-- 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