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.
--oh. Well, in that case, your answer will depend on your choice of s, and hence be kind of arbitrary and ugly and pointless to compute. (?) --- But anyhow, generate a random uniform (from your measure) start-pattern, run golly, and use Floyd cycle finding algorithm to see if it has settled into a cycle (a), and use special code to detect whether some glider or spaceship has "escaped" (b). Prob(a) is a lower bound on your probability Pstay, Prob(b) is a lower bound on 1-Pstay. So you can compute confidence intervals for both lower & upper bounds. Or: can you? In order to compute Prob(b) you need to KNOW whether some glider or spaceship has escaped. How do you know that? If we knew that nothing could travel diagonally faster than a glider, or knew nothing could travel horizontally faster than a spaceship, then maybe we could prove escape. However, I am unaware of any such proof. I.e. it might not have really escaped -- something faster will come along later to catch and kill it. In view of this, I do not see a good way to prove good upper bounds, I only see how to prove lower bounds? Well... if you can detect a situation with escaped gliders and the rest is periodic, then for THAT we can prove escape, thus getting upper bounds.