[Link] Does a Simulation Really Need to Be Run?
post by VincentYu · 2011-06-22T23:28:18.081Z · LW · GW · Legacy · 17 commentsContents
17 comments
http://blog.regehr.org/archives/546
John Regehr, an associate professor of computer science at the University of Utah, writes about two algorithmic optimizations for Conway's Game of Life, and speculates on the implications for self-aware entities in simulations.
Hashlife is a clever optimization that treats the Life grid as a hierarchy of quadtrees. By observing that the maximum speed of signal propagation in a Life configuration is one cell per step, it becomes possible to evolve squares of the Life grid multiple steps into the future using hash codes. Hashlife is amazing to watch: it starts out slow but as the hashtable fills up, it suddenly “explodes” into exponential progress. I recommend Golly. Hashlife is one of my ten all-time favorite algorithms.
Those who have read Greg Egan's Permutation City will find the concept of Hashlife familiar.
Another ingenious simulation speedup (developed, as it happens, around the same time as Hashlife) is Time Warp, which relaxes the synchronization requirements, permitting a processor to run well ahead of its neighbors. This opens up the possibility that a processor will at some point receive a message that violates causality: it needs to be executed in the past. Clearly this is a problem. The solution is to roll back the simulation state to the time of the message and resume execution from there. If rollbacks are infrequent, overall performance may increase due to improved asynchrony. This is a form of “optimistic concurrency” and it can be shown to preserve the meaning of a simulation in the sense that the Time Warp implementation must always return the same final answer as the non-optimistic implementation.
17 comments
Comments sorted by top scores.
comment by jasonmcdowell · 2011-06-23T05:37:33.883Z · LW(p) · GW(p)
My favorite large CGoL object is the MetaPixel. It is a life object implementing a life unit cell, which actually looks like a life unit cell when zoomed out. A copy of it and some meta-simulations come with Golly.
http://www.conwaylife.com/wiki/OTCA_metapixel
Replies from: Xachariah↑ comment by Xachariah · 2011-06-23T18:20:56.523Z · LW(p) · GW(p)
One day science will uncover hidden binary buried deep in the Golden Ratio. Converting to text it reads...
// const int speed_of_light = 512 planck units over 1 planck time // do NOT let anything go faster than that or it'll crash the rendering system -G // what about gravity wells? -S // screw it we need to ship, just give them them a time slow -G
comment by D_Alex · 2011-06-23T04:20:40.792Z · LW(p) · GW(p)
It is eerie to consider that the reason for existence of some physical phenomena is explainable if one supposes that our universe is built upon a CGoL-type substrate. Examples:
- the uni-directionality of time
- the light-speed limit
- the observer effect
A rich source of material for philosophical speculation!
Replies from: Manfred, Xachariah, benelliott, DanielLC↑ comment by Manfred · 2011-06-23T07:57:00.726Z · LW(p) · GW(p)
Careful not to privilege hypotheses - the game of life's fame is not correlated with it's use as a theory of everything, at last not when you compare it to the zillions of other systems that have very similar properties. So allll those non-famous systems are probably just as good.
Philosophical speculation should still be grounded, since we don't have time to consider every possibility ever.
Replies from: D_Alex↑ comment by D_Alex · 2011-06-23T09:05:18.863Z · LW(p) · GW(p)
Careful not to fall prey to the Sorites Paradox - where exactly is the line between insufficient and sufficient evidence to form a hypothesis?
I should clarify that by CGoL-type substrate I meant some kind of 3-D cellular automaton, clearly not the 2-D CGoL itself. Other people, e.g. Stephen Wolfram and Konrad Zuse have seen fit to speculate at length on this subject.
Replies from: VincentYu, timtyler, Manfred↑ comment by VincentYu · 2011-06-23T14:30:02.491Z · LW(p) · GW(p)
Do Wolfram and Zuse speculate that there is a correspondence between cells in the cellular automaton and space in our universe, or do they speculate that our universe is being computed (at a high-level) by a cellular automaton? In other words, at what level does the correspondence between our universe and the cellular automaton exist?
In the former case, where there is a low-level correspondence, we can expect the properties of the cellular automaton, i.e.,
- the uni-directionality of time
- the light-speed limit
- the observer effect
to have a similar physical meaning in our universe.
However, in the second case, which seems more reasonable to me, I don't see how these specific properties of the cellular automaton will have anything to do with the properties of our universe.
Replies from: D_Alex, Perplexed↑ comment by timtyler · 2011-06-26T20:16:19.267Z · LW(p) · GW(p)
Other people, e.g. Stephen Wolfram and Konrad Zuse have seen fit to speculate at length on this subject.
Indeed. I have a domain devoted to digital physics: http://finitenature.com/
↑ comment by Manfred · 2011-06-23T18:24:43.710Z · LW(p) · GW(p)
Careful not to fall prey to the Sorites Paradox - where exactly is the line between insufficient and sufficient evidence to form a hypothesis?
Sufficient evidence to promote and think more about a hypothesis (we weren't talking about "forming" before) is when the expected value of so promoting and thinking is positive. So for example, I wouldn't spend much philosophical speculation on the idea that the universe is actually running on a really big computer with the operating system Windows XP. It's possible, it has lots of nice properties, but it's simply not worth the energy of even writing a blog post about.
But yeah, sure, if by "like the game of life" you meant "any system that's local and discrete in space and time," then that's an nigh-infinitely bigger chunk of hypothesis-space, and I won't knock it.
↑ comment by Xachariah · 2011-06-23T18:21:40.176Z · LW(p) · GW(p)
One day science will uncover hidden binary buried deep in the Golden Ratio. Converting to text it reads...
Replies from: JoshuaZ// const int speedOfLight = 512 planck units over 1 planck time
// do NOT let anything go faster than that or it'll crash the rendering system -G
// what about gravity wells? -S
// screw it we need to ship, just give them them the time slow field
// besides, until version 2.0 anything going that fast has to be hacking -G
↑ comment by JoshuaZ · 2011-06-23T22:10:38.622Z · LW(p) · GW(p)
If one saw this inside the fine structure constant or some other parameter that is universe dependent that would be more plausible than in the golden ratio, since that's a ratio that is created by a simple calculation and so should be the same throughout all universes.
↑ comment by benelliott · 2011-06-24T10:29:09.258Z · LW(p) · GW(p)
the uni-directionality of time
Is a constraint we imposed on it, when Conway invented life he was only considering unidirectional time systems.
the light-speed limit
Is a consequence of locality, which was also something we imposed because of convenience rather than something we discovered
the observer effect
Does not exist in life, I've seen a rather complex configuration that allows gliders to pass and detects them but does not interfere with their path in any way.
Replies from: D_Alex↑ comment by D_Alex · 2011-06-28T05:16:42.671Z · LW(p) · GW(p)
the uni-directionality of time
Is a constraint we imposed on it, when Conway invented life he was only considering unidirectional time systems.
It's a consequence of the fact that you just cannot compute Life backward, because it is indeterminate.
the light-speed limit
Is a consequence of locality, which was also something we imposed
Not sure I understand you... is it possible not to impose that in a cellular automaton?
the observer effect
Does not exist in life, I've seen a rather complex configuration that allows gliders to pass and detects them but does not interfere with their path in any way.
You may well be right, on reflection it seems theoretically possible.
You use "we" in your post in a way that implies you co-developed Life - is that correct?
Replies from: benelliott↑ comment by benelliott · 2011-06-28T10:57:55.097Z · LW(p) · GW(p)
I think you could allow non-local influences if you wanted, although if you define cellular automaton in a certain way it would no longer count as one.
As for the first, I think that assuming you take MWI rather than Collapse theories our universe can be computed backwards at the bottom level (if you take Collapse then you run into other problems, since life is both deterministic and local whereas collapse isn't).
For the record, I did not co-develop life (it pre-dates my birth by several decades), and I did not intend to imply that I had.
↑ comment by DanielLC · 2011-06-23T22:38:07.271Z · LW(p) · GW(p)
I think time results from anything that uses boundary conditions. Timeless quantum physics doesn't have time as an explicit dimension, and there's no obvious way to say which direction time flows in, but it still manages to add up to normality.
What does the observer effect have to do with it? Do you mean that something in CGoL can't detect stuff without interfering with it? That doesn't require much.
My main problem is that cellular automata would be very unlikely to rotationally symmetric.