4 ms·

One thing that comes to mind is reversible computing. (https://en.wikipedia.org/wiki/Reversible_computing https://en.wikipedia.org/wiki/Reversible_computing). W

by fbrusch 10y ago

One thing that comes to mind is reversible computing. (https://en.wikipedia.org/wiki/Reversible_computing https://en.wikipedia.org/wiki/Reversible_computing). When computation is irreversible (as is the case for all our current information elaboration systems and substrates), it is bounded below in the energy that dissipates. The bound is quantified by the Landauer principle, and has to do with the entropy involved in "forgetting" the previous states. If a computation process is reversible, it doesn't incur in such limit. One can maybe imagine time crystals concocted to carry out useful computation, spending no energy in the process.

DonHopkins 10y ago
Tommaso Toffoli [1] invented the reversible Toffoli Gate [2]. Norman Margolus [3] invented the Margolus Neighborhood [4], which is useful for rotationally symmetrical cellular automata rules [5] like billiard ball cellular automata [6] [7]. Toffoli and Margolus also explored other energy conserving cellular automata like spin glasses [8], which are disordered magnets that store energy in the bonds between atoms. Edward Fredkin [9] invented reversible second order cellular automata [10], which look back two steps in time, and are useful for simulating the Ising model of ferromagnetism. Then again, maybe Otis Eugene "Gene" Ray, the "wisest man on earth", caused this article to quantum tunnel through time from April 1 1997 [11] [12]. To play with the following code that implements a spin glass, go here: http://donhopkins.com/home/CAM6/ http://donhopkins.com/home/CAM6/ then click the square in the upper left, click "Rules", pick the rule "von Neumann Spins Only", and draw in the cells by dragging around with the left button. JavaScript sure cooks these days! // ruleFunction_VonNeumann_spinsOnly computes the Spins Only rule // for VonNeumann neighborhood lookup table. // // Cellular Automata Machines, p. 190, section 17.3, Spins Only. // // This models a spin glass, which is a matrix of atoms with // magnetic spins (up or down). // // https://en.wikipedia.org/wiki/Spin_glass // // A spin glass is a disordered magnet with frustrated // interactions, augmented by stochastic positions of the spins, // where conflicting interactions, namely both ferromagnetic and // also antiferromagnetic bonds, are randomly distributed with // comparable frequency. The term "glass" comes from an analogy // between the magnetic disorder in a spin glass and the // positional disorder of a conventional, chemical glass, e.g., // a window glass. // // Spin glasses display many metastable structures, leading to a // plenitude of time scales which are difficult to explore // experimentally or in simulations. // function ruleFunction_VonNeumann_spinsOnly(ruleDict, state) { // This makes a checkerboard pattern that alternates every // step, so we can apply the rule to every other cell every // other step. That way we know our four neighbors will not be // changing at the same time we are changing. var activeSite = (state.horiz ^ state.phaseTime) == state.vert; // Count how many of our four neighbors are set. var sum4 = state.n0 + state.w0 + state.e0 + state.s0; // When it is our turn to run in this cell (at every other // step), then we flip our value if exactly two of our // neighbors are up, and two are down. Since energy is stored // in two adjacent cells with different spins, we can flip our // value without changing the energy of the system, because // the perimeter between up and down cells remains the same. var result = (activeSite ? [ state.c0, state.c0, state.c0 ^ 1, state.c0, state.c0 ][sum4] : state.c0); return result; } [1] https://en.wikipedia.org/wiki/Tommaso_Toffoli https://en.wikipedia.org/wiki/Tommaso_Toffoli [2] https://en.wikipedia.org/wiki/Toffoli_gate https://en.wikipedia.org/wiki/Toffoli_gate [3] https://en.wikipedia.org/wiki/Norman_Margolus https://en.wikipedia.org/wiki/Norman_Margolus [4] https://github.com/SimHacker/CAM6/blob/master/javascript/CAM6.js#L4282 https://github.com/SimHacker/CAM6/blob/master/javascript/CAM... [5] https://github.com/SimHacker/CAM6/blob/master/javascript/CAM6.js#L5636 https://github.com/SimHacker/CAM6/blob/master/javascript/CAM... [6] https://en.wikipedia.org/wiki/Reversible_cellular_automaton#Billiard_ball_computation_and_low-power_computing https://en.wikipedia.org/wiki/Reversible_cellular_automaton#... [7] https://en.wikipedia.org/wiki/Billiard-ball_computer https://en.wikipedia.org/wiki/Billiard-ball_computer [8] https://en.wikipedia.org/wiki/Spin_glass https://en.wikipedia.org/wiki/Spin_glass [9] https://en.wikipedia.org/wiki/Edward_Fredkin https://en.wikipedia.org/wiki/Edward_Fredkin [10] https://en.wikipedia.org/wiki/Second-order_cellular_automaton https://en.wikipedia.org/wiki/Second-order_cellular_automato... [11] https://en.wikipedia.org/wiki/Time_Cube https://en.wikipedia.org/wiki/Time_Cube [12] https://web.archive.org/web/19980629180418/http://www.timecube.com/ https://web.archive.org/web/19980629180418/http://www.timecu...
- throwawayish 10y ago
  Twelve citations in a HN comment has to be some kind of record.
  - deleted 10y ago
    [deleted]
  - DonHopkins 10y ago
    I was only getting started! There are so many much more interesting cellular automata than Life, which is so overrated. As Marvin the Paranoid Android says, "Life? Don't talk to me about life! Loathe it or ignore it. You can't like it." The classic book on the subject is "Cellular Automata Machines: A New Environment for Modeling" [1] This article has a lot of great references: "When–and how–can a cellular automaton be rewritten as a lattice gas?" [2]. And Fredkin's "Digital Mechanics: An Informational Process Based on Reversible Universal Cellular Automata" [3] is also a classic paper about the subject. Fredkin, Toffoli, Margolus and others have done a lot of interesting research into reversible computation, which has many practical and theological [4] applications, and will some day be very useful at the Restaurant at the End of the Universe [5]. [1] https://mitpress.mit.edu/books/cellular-automata-machines https://mitpress.mit.edu/books/cellular-automata-machines [2] http://www.sciencedirect.com/science/article/pii/S0304397508003629?np=y&npKey=9d7c391743e27ff27ce1020a5bb9f3cdf2223427de10ab1b2e6e1d0523704429 http://www.sciencedirect.com/science/article/pii/S0304397508... [3] https://books.google.com/books?id=6o6zx5MRRcQC&pg=PA254&lpg=PA254&dq=fredkin+%22Digital+Mechanics:+An+Informational+Process+Based+on+Reversible+Universal+Cellular+Automata%22&source=bl&ots=n13CPseK8q&sig=k7VesMLt0hjQtl_7u5Oedh3E0-o&hl=en&sa=X&ved=0ahUKEwi-teb_lOXRAhUD0WMKHX1BAIQQ6AEINTAD#v=onepage&q=fredkin%20%22Digital%20Mechanics%3A%20An%20Informational%20Process%20Based%20on%20Reversible%20Universal%20Cellular%20Automata%22&f=false https://books.google.com/books?id=6o6zx5MRRcQC&pg=PA254&lpg=... [4] http://www.tandfonline.com/doi/pdf/10.1080/15665399.2010.10820012 http://www.tandfonline.com/doi/pdf/10.1080/15665399.2010.108... [5] https://en.wikipedia.org/wiki/Omega_Point https://en.wikipedia.org/wiki/Omega_Point

by fbrusch 10y ago

DonHopkins 10y ago

Tommaso Toffoli [1] invented the reversible Toffoli Gate [2]. Norman Margolus [3] invented the Margolus Neighborhood [4], which is useful for rotationally symmetrical cellular automata rules [5] like billiard ball cellular automata [6] [7]. Toffoli and Margolus also explored other energy conserving cellular automata like spin glasses [8], which are disordered magnets that store energy in the bonds between atoms. Edward Fredkin [9] invented reversible second order cellular automata [10], which look back two steps in time, and are useful for simulating the Ising model of ferromagnetism. Then again, maybe Otis Eugene "Gene" Ray, the "wisest man on earth", caused this article to quantum tunnel through time from April 1 1997 [11] [12]. To play with the following code that implements a spin glass, go here: http://donhopkins.com/home/CAM6/ http://donhopkins.com/home/CAM6/ then click the square in the upper left, click "Rules", pick the rule "von Neumann Spins Only", and draw in the cells by dragging around with the left button. JavaScript sure cooks these days! // ruleFunction_VonNeumann_spinsOnly computes the Spins Only rule // for VonNeumann neighborhood lookup table. // // Cellular Automata Machines, p. 190, section 17.3, Spins Only. // // This models a spin glass, which is a matrix of atoms with // magnetic spins (up or down). // // https://en.wikipedia.org/wiki/Spin_glass // // A spin glass is a disordered magnet with frustrated // interactions, augmented by stochastic positions of the spins, // where conflicting interactions, namely both ferromagnetic and // also antiferromagnetic bonds, are randomly distributed with // comparable frequency. The term "glass" comes from an analogy // between the magnetic disorder in a spin glass and the // positional disorder of a conventional, chemical glass, e.g., // a window glass. // // Spin glasses display many metastable structures, leading to a // plenitude of time scales which are difficult to explore // experimentally or in simulations. // function ruleFunction_VonNeumann_spinsOnly(ruleDict, state) { // This makes a checkerboard pattern that alternates every // step, so we can apply the rule to every other cell every // other step. That way we know our four neighbors will not be // changing at the same time we are changing. var activeSite = (state.horiz ^ state.phaseTime) == state.vert; // Count how many of our four neighbors are set. var sum4 = state.n0 + state.w0 + state.e0 + state.s0; // When it is our turn to run in this cell (at every other // step), then we flip our value if exactly two of our // neighbors are up, and two are down. Since energy is stored // in two adjacent cells with different spins, we can flip our // value without changing the energy of the system, because // the perimeter between up and down cells remains the same. var result = (activeSite ? [ state.c0, state.c0, state.c0 ^ 1, state.c0, state.c0 ][sum4] : state.c0); return result; } [1] https://en.wikipedia.org/wiki/Tommaso_Toffoli https://en.wikipedia.org/wiki/Tommaso_Toffoli [2] https://en.wikipedia.org/wiki/Toffoli_gate https://en.wikipedia.org/wiki/Toffoli_gate [3] https://en.wikipedia.org/wiki/Norman_Margolus https://en.wikipedia.org/wiki/Norman_Margolus [4] https://github.com/SimHacker/CAM6/blob/master/javascript/CAM6.js#L4282 https://github.com/SimHacker/CAM6/blob/master/javascript/CAM... [5] https://github.com/SimHacker/CAM6/blob/master/javascript/CAM6.js#L5636 https://github.com/SimHacker/CAM6/blob/master/javascript/CAM... [6] https://en.wikipedia.org/wiki/Reversible_cellular_automaton#Billiard_ball_computation_and_low-power_computing https://en.wikipedia.org/wiki/Reversible_cellular_automaton#... [7] https://en.wikipedia.org/wiki/Billiard-ball_computer https://en.wikipedia.org/wiki/Billiard-ball_computer [8] https://en.wikipedia.org/wiki/Spin_glass https://en.wikipedia.org/wiki/Spin_glass [9] https://en.wikipedia.org/wiki/Edward_Fredkin https://en.wikipedia.org/wiki/Edward_Fredkin [10] https://en.wikipedia.org/wiki/Second-order_cellular_automaton https://en.wikipedia.org/wiki/Second-order_cellular_automato... [11] https://en.wikipedia.org/wiki/Time_Cube https://en.wikipedia.org/wiki/Time_Cube [12] https://web.archive.org/web/19980629180418/http://www.timecube.com/ https://web.archive.org/web/19980629180418/http://www.timecu...

throwawayish 10y ago
Twelve citations in a HN comment has to be some kind of record.
- deleted 10y ago
  [deleted]
- DonHopkins 10y ago
  I was only getting started! There are so many much more interesting cellular automata than Life, which is so overrated. As Marvin the Paranoid Android says, "Life? Don't talk to me about life! Loathe it or ignore it. You can't like it." The classic book on the subject is "Cellular Automata Machines: A New Environment for Modeling" [1] This article has a lot of great references: "When–and how–can a cellular automaton be rewritten as a lattice gas?" [2]. And Fredkin's "Digital Mechanics: An Informational Process Based on Reversible Universal Cellular Automata" [3] is also a classic paper about the subject. Fredkin, Toffoli, Margolus and others have done a lot of interesting research into reversible computation, which has many practical and theological [4] applications, and will some day be very useful at the Restaurant at the End of the Universe [5]. [1] https://mitpress.mit.edu/books/cellular-automata-machines https://mitpress.mit.edu/books/cellular-automata-machines [2] http://www.sciencedirect.com/science/article/pii/S0304397508003629?np=y&npKey=9d7c391743e27ff27ce1020a5bb9f3cdf2223427de10ab1b2e6e1d0523704429 http://www.sciencedirect.com/science/article/pii/S0304397508... [3] https://books.google.com/books?id=6o6zx5MRRcQC&pg=PA254&lpg=PA254&dq=fredkin+%22Digital+Mechanics:+An+Informational+Process+Based+on+Reversible+Universal+Cellular+Automata%22&source=bl&ots=n13CPseK8q&sig=k7VesMLt0hjQtl_7u5Oedh3E0-o&hl=en&sa=X&ved=0ahUKEwi-teb_lOXRAhUD0WMKHX1BAIQQ6AEINTAD#v=onepage&q=fredkin%20%22Digital%20Mechanics%3A%20An%20Informational%20Process%20Based%20on%20Reversible%20Universal%20Cellular%20Automata%22&f=false https://books.google.com/books?id=6o6zx5MRRcQC&pg=PA254&lpg=... [4] http://www.tandfonline.com/doi/pdf/10.1080/15665399.2010.10820012 http://www.tandfonline.com/doi/pdf/10.1080/15665399.2010.108... [5] https://en.wikipedia.org/wiki/Omega_Point https://en.wikipedia.org/wiki/Omega_Point