[math-fun] Life probability of halting/settling
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.
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
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
On Sun, Jun 24, 2012 at 8:29 PM, Robert Munafo <mrob27@gmail.com> wrote:
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?
The measure is a function from patterns (or natural numbers, since the patterns are enumerable) to real numbers such that the sum over all patterns is finite. The one Michael Kleber described is a perfectly valid measure. My ideal measure would still assign 2^{-s|p|} or 2^{-s ln(index(p))} to each pattern p, since then I still get a partially random real out at computable s, but the cells would be numbered in a way that makes computing the measure of equivalent patterns relatively easy. Does numbering them in an order traced out by a space-filling curve like a Hilbert curve or a dragon curve give any benefits over using a spiral? -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
Okay, so far so good. On 6/25/12, Mike Stay <metaweta@gmail.com> wrote:
My ideal measure would still assign 2^{-s|p|} or [...]
|p| looks like "absolute value of p" so I guess that's your shorthand for the measure function. What is s?
[...] or 2^{-s ln(index(p))} to each pattern p, since then I still get a partially random real out at computable s, but the cells would be numbered in a way that makes computing the measure of equivalent patterns relatively easy. Does numbering them in an order traced out by a space-filling curve like a Hilbert curve or a dragon curve give any benefits over using a spiral?
I numbered my cells for a different purpose, but I had a similar motivation (making it so that equivalent rotations and reflections could be somehow ignored, and having the first N integers lie within a roughly sqrt(N) sized part of the grid). At least I think that's your motivation (-: Anyway, I couldn't think of much that was better than "antidiagonals", which is no better than spirals. I always normalized patterns by sliding them into a corner, so antidiagonals makes more sense. If you normalize by "centering" the pattern on the origin, then a spiral centered on the origin would make sense. -- 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
On Sun, Jun 24, 2012 at 10:36 PM, Robert Munafo <mrob27@gmail.com> wrote:
Okay, so far so good.
On 6/25/12, Mike Stay <metaweta@gmail.com> wrote:
My ideal measure would still assign 2^{-s|p|} or [...]
|p| looks like "absolute value of p" so I guess that's your shorthand for the measure function. What is s?
p is a binary string laid out in a spiral (say) to form the life pattern and |p| is the length of the binary string. s is a real number, usually taken to be computable and greater than 1, but can be left as a free parameter.
[...] or 2^{-s ln(index(p))}
The sum zeta(s) = sum_p 2^{-s lg(index(p))} is another way of writing the Riemann zeta function. The sum sum_p h(p) 2^{-s lg(index(p))} / zeta(s), where h(p) is 1 if it eventually dies out and 0 otherwise, is the Dirichlet generating function for h(p), also known as "the halting probability at inverse temperature s." It converges at s > 1 and gives a partially random real number at computable s > 1. That partially random real is compressible by a factor of s.
to each pattern p, since then I still get a partially random real out at computable s, but the cells would be numbered in a way that makes computing the measure of equivalent patterns relatively easy. Does numbering them in an order traced out by a space-filling curve like a Hilbert curve or a dragon curve give any benefits over using a spiral?
I numbered my cells for a different purpose, but I had a similar motivation (making it so that equivalent rotations and reflections could be somehow ignored, and having the first N integers lie within a roughly sqrt(N) sized part of the grid). At least I think that's your motivation (-: Anyway, I couldn't think of much that was better than "antidiagonals", which is no better than spirals. I always normalized patterns by sliding them into a corner, so antidiagonals makes more sense. If you normalize by "centering" the pattern on the origin, then a spiral centered on the origin would make sense.
That's good to know, thanks! -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
participants (3)
-
Mike Stay -
Robert Munafo -
Warren Smith