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?
--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. (?)
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.
But anyhow, generate a random uniform (from your measure)
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.
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?
I'm happy to start with states that are easy to detect. That said, you can prove lower bounds by showing that a set of patterns reaches the state you care about. You can prove upper bounds by showing that a set of patterns grows unboundedly. The number itself is only computably enumerable, so for each formal axiomatic system, only a finite prefix of the value of the partition function is provable: one cannot prove better and better upper bounds without constantly having fundamentally new insights. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com