http://wiki.karljones.com/index.php?action=history&feed=atom&title=Reversible_cellular_automaton 2026-10-23T13:36:25Z Revision history for this page on the wiki MediaWiki 1.24.2 http://wiki.karljones.com/index.php?title=Reversible_cellular_automaton&diff=18788&oldid=prev 2016-09-24T01:59:57Z

<p>Created page with &quot;A &#039;&#039;&#039;reversible cellular automaton&#039;&#039;&#039; is a <a href="/index.php/Cellular_automaton" title="Cellular automaton">cellular automaton</a> in which every configuration has a unique predecessor. That is, it is a regular grid of cells, each containi...&quot;</p> <p><b>New page</b></p><div>A '''reversible cellular automaton''' is a [[cellular automaton]] in which every configuration has a unique predecessor.<br /> <br /> That is, it is a regular grid of cells, each containing a state drawn from a finite set of states, with a rule for updating all cells simultaneously based on the states of their neighbors, such that the previous state of any cell before an update can be determined uniquely from the updated states of all the cells.<br /> <br /> == Description ==<br /> <br /> The [[Time reversibility|time-reversed dynamics]] of a reversible cellular automaton can always be described by another cellular automaton rule, possibly on a much larger neighborhood.<br /> <br /> Several methods are known for defining cellular automata rules that are reversible; these include the [[block cellular automaton]] method, in which each update partitions the cells into blocks and applies an invertible function separately to each block, and the [[second-order cellular automaton]] method, in which the update rule combines states from two previous steps of the automaton.<br /> <br /> When an automaton is not defined by one of these methods, but is instead given as a rule table, the problem of testing whether it is reversible is solvable for block cellular automata and for one-dimensional cellular automata, but is [[Undecidable problem|undecidable]] for other types of cellular automata.<br /> <br /> Reversible cellular automata form a natural model of [[reversible computing]], a technology that could lead to ultra-low-power computing devices.<br /> <br /> [[Quantum cellular automaton|Quantum cellular automata]], one way of performing computations using the principles of quantum mechanics, are often required to be reversible. Additionally, many problems in physical modeling, such as the motion of particles in an ideal gas or the Ising model of alignment of magnetic charges, are naturally reversible and can be simulated by reversible cellular automata.<br /> <br /> Properties related to reversibility may also be used to study cellular automata that are not reversible on their entire configuration space, but that have a subset of the configuration space as an [[attractor]] that all initially random configurations converge towards. As [[Stephen Wolfram]] writes, &quot;once on an attractor, any system—even if it does not have reversible underlying rules—must in some sense show approximate reversibility.&quot;<br /> <br /> == See also ==<br /> <br /> * [[Block cellular automaton]]<br /> * [[Cellular automaton]]<br /> * [[Second-order cellular automaton]]<br /> <br /> == External links ==<br /> <br /> * [https://en.wikipedia.org/wiki/Reversible_cellular_automaton Reversible cellular automaton] @ Wikipedia<br /> <br /> [[Category:Cellular automata]]<br /> [[Category:Computation]]<br /> [[Category:Mathematics]]</div>

Karl Jones