[math-fun] "Life: probability of halting or settling
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 mean, if you were running life on some finite-size grid-torus, then it would be nonzero but... 1. on an infinite grid, there will with prob=1 be some unboundedly large region of the grid containing the worst possible pattern it could contain, which will last for time>=T before you regard it as settled, where T can be made unboundedly large. 2. Returning to the finite-size grid-torus, since there are only a finite set of states, the thing is certain to be periodic, so then the probability is 1.
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
participants (2)
-
Mike Stay -
Warren Smith