A 1D reversible cellular automaton plays and finishes Charles Bennett's pebble game.

Reversible computation is the art of computing while deleting little to no information in the process of computation.
Landauer's principle states that computation must expend at least k*T*ln(2) energy for each bit of information deleted. Here, T is the temperature, and k is Boltzmann's constant. k=1.38*10^(-23)Joules/Kelvin. In practice, we should expect for all forms of irreversible computation much more than k*T*ln(2) per bit deleted. Reversible computation gets around the k*T*ln(2) energy cost per bit deleted by deleting little to no information. But since reversible computation is a restricted form of computation, it almost always takes more operations to perform a calculation on a reversible computer than it does on a conventional irreversible computer. Fortunately, thanks to optimal strategies for playing Bennett's pebble game, the computational overhead incurred from reversibility is surmountable.
Bennett's pebble game is the following 1 player game. Suppose that one has S pebbles and a board with n spaces which we shall label Space 1,...,Space n. The objective of the game is to move in as few moves as possible to a state with a pebble on Space 1, a pebble on Space n, and no other pebbles on the board. The starting position of Bennett's pebble game consists of a pebble on Space 1 and no other pebbles on the board. In Bennett's pebble game, one is allowed to place or remove a pebble on Space j if and only if there is a pebble on Space j-1, and no other moves are valid. Bennett's pebble game is a model of reversible computation simulating an irreversible computation. Bennett's pebble game can be generalized in many ways to digraphs and to model partially reversible computation and parallel computation. The original version of Bennett's pebble game was originally completely solved by Emanuel Knill's 1995 paper 'An analysis of Bennett's pebble game'.
In this visualization, we use a 1D cellular automaton to simulate Bennett's pebble game where n=62 and S=16. The pebbles on the board are colored yellow. The pebbles that are next to a space on the board are colored blue. If there is a pebble on Space j and another pebble next to Space j, then we color that space white as white is the additive combination of blue and yellow. In this cellular automaton, the total number of pebbles on and next to the board is conserved, and this cellular automaton abides by the rules of Bennett's pebble game. This cellular automaton is also completely reversible.
Here we run the visualization until it completes Bennett's pebble game in the sense that there is a pebble on Space n, but in this visualization, there are plenty of other pebbles on the board.
While the reversible cellular automaton completes Bennett's pebble game in a sense, the reversible cellular automaton is not making intelligent moves to complete Bennett's pebble game since I did not train this cellular automaton to have any artificial intelligence in it (and the reversibility of the cellular automaton restricts the ability for any cellular automaton to make intelligent moves).
The notion of a reversible cellular automaton is not my own, but I designed this reversible cellular automaton myself to play Bennett's pebble game. While this cellular automaton plays Bennett's pebble game unintelligently, it may be possible to use evolutionary computation to construct a (likely irreversible) cellular automaton that plays generalizations of Bennett's pebble game intelligently, but I have not tried to do this, so I don't know how well this would work.
Unless otherwise stated, all algorithms featured on this channel are my own. You can go to github.com/spo... to support my research on machine learning algorithms. I am also available to consult on the use of safe and interpretable AI for your business. I am designing machine learning algorithms for AI safety such as LSRDRs. In particular, my algorithms are designed to be more predictable and understandable to humans than other machine learning algorithms, and my algorithms can be used to interpret more complex AI systems such as neural networks. With more understandable AI, we can ensure that AI systems will be used responsibly and that we will avoid catastrophic AI scenarios. There is currently nobody else who is working on LSRDRs, so your support will ensure a unique approach to AI safety.

[@josephvanname3377]

Reversible computation is the future.