{"id":7099,"date":"2013-05-11T14:33:18","date_gmt":"2013-05-11T21:33:18","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=7099"},"modified":"2013-05-11T14:33:18","modified_gmt":"2013-05-11T21:33:18","slug":"a-paradox-of-tooms-rule","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2013\/05\/11\/a-paradox-of-tooms-rule\/","title":{"rendered":"A Paradox of Toom's Rule?"},"content":{"rendered":"

Science is slow. \u00a0You can do things like continue a conversation<\/a>\u00a0with yourself (and a few commenters) that started in 2005. \u00a0Which is what I’m now going to do \ud83d\ude42 \u00a0The below is probably a trivial observation for one of the cardinals<\/a>, but I find it kind of interesting.
\nLet’s begin by recalling the setup. \u00a0Toom’s rule is a cellular automata rule for a two dimensional cellular automata on a square grid. \u00a0Put +1 and -1’s on the vertices of a square grid, and then use the following update rule at each step: “Update the value with the majority vote of your own state, the state of your neighbor to the north, and the state of your neighbor to the east.” \u00a0A few steps of the rule are shown here with +1 as white and -1 as blue:
\n\"Toom's<\/a>As you can see Toom’s rule “shrinks” islands of “different” states (taking away such different cells from the north and east sides of such an island.) \u00a0It is this property which gives Toom’s rule some cool properties in the presence of noise.
\nSo now consider Toom’s rule, but with noise. \u00a0Replace Toom’s update rule with the rule followed by, for each and every cell a noise process. \u00a0For example this noise could be to put the cell into state +1 with p percent probability and -1 with q percent probability. \u00a0Suppose now you are trying to store information in the cellular automata. \u00a0You start out at time zero, say, in the all +1 state. \u00a0Then let Toom’s rule with noise run. \u00a0If p=q and these values are below a threshold, then if you start in the +1 state you will remain in a state with majority +1 with a probability that goes to one exponentially as a function of the system size. \u00a0Similarly if you start in -1. \u00a0The cool thing about Toom’s rule is that this works not just for p=q, but also for some values of p not equal to q (See here for a picture of the phase diagram.) \u00a0That is there are two stable states in this model, even for biased noise.
\nContrast Toom’s rule with a two dimensional Ising model which is in the process of equilibriating to temperature T. \u00a0If this model has no external field applied, then like Toom’s rule there is a phase where the mostly +1 and the mostly -1 states are stable and coexist. \u00a0These are from zero temperature (no dynamics) to a threshold temperature T, the critical temperature of the Ising model. But, unlike in Toom’s rule, if you now add an external field, which corresponds to a dynamics where there is now a greater probability of flipping the cell values to a particular value (p not equal to q above), then the Ising model no longer has two stable phases.
\nIn fact there is a general argument that if you look at a phase diagram as a function of a bunch of parameters (say temperature and applied magnetic field strength in this case), then the places where two stable regimes can coexist has to be a surface with one less dimension than your parameter space. \u00a0This is known as Gibbs’ phase rule<\/a>. \u00a0Toom’s rule violates this. \u00a0It’s an example of a nonequilibrium system.
\nSo here is what is puzzling me. \u00a0Consider a three dimensional cubic lattice with +1,-1 spins on its vertices. Define an energy function that is a sum over terms that act on the spins on locations (i,j,k), (i+1,j,k), (i,j+1,k), (i,j,k+1) such that E = 0 if the spin at (i,j,k+1) is in the correct state for Toom’s rule applied to spins (i,j,k), (i+1,j,k), and (i,j+1,k) and is J otherwise. \u00a0In other words the terms enforce that the ground state locally obey’s Toom’s rule, if we imagine rolling out Toom’s rule into the time dimension (here the z direction). At zero temperature, the ground state of this system will be two-fold degenerate corresponding to the all +1 and all -1 state. \u00a0At finite temperature this model well behave as a symmetric noise Toom’s rule model (see here<\/a> for why.) \u00a0So even at finite temperature this will preserve information, like the d>2 Ising model and Toom’s CA rule.
\nBut since this behaves like Toom’s rule, it seems to me that if you add an external field, then this system is in a bit of paradox. \u00a0On the one hand, we know from Gibb’s phase rule, that this should not be able to exhibit two stable phases over a range of external fields. \u00a0On the other hand, this thing is just Toom’s rule, laid out spatially. \u00a0So it would seem that one could apply the arguments about why Toom’s rule is robust at finite field. \u00a0But these contradict each other. \u00a0So which is it?
\n <\/p>\n","protected":false},"excerpt":{"rendered":"

Science is slow. \u00a0You can do things like continue a conversation\u00a0with yourself (and a few commenters) that started in 2005. \u00a0Which is what I’m now going to do \ud83d\ude42 \u00a0The below is probably a trivial observation for one of the cardinals, but I find it kind of interesting. Let’s begin by recalling the setup. \u00a0Toom’s … <\/p>\n

Continue reading “A Paradox of Toom's Rule?”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[53],"tags":[],"class_list":["post-7099","post","type-post","status-publish","format-standard","hentry","category-physics"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/7099","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/comments?post=7099"}],"version-history":[{"count":0,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/7099\/revisions"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/media?parent=7099"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/categories?post=7099"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/tags?post=7099"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}