On Sun, Jun 24, 2012 at 1:11 PM, Warren Smith <warren.wds@gmail.com> wrote:
From: Mike Stay <metaweta@gmail.com> 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?
--but isn't this probability zero?
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. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com