Sliding Blocks Computing

Paper by Robert A. Hearn (2003)

Consider the AND mini-puzzle. Suppose the goal is to slide the upper protruding block into the box? The answer is that first the left block and the bottom block must both be slid out one unit. This will let the internal blocks slide to free up space for the upper block to slide in.

So, this puzzle does indeed have an AND-like property: both the left and the bottom blocks must slide out before the top one may slide in. The light gray blocks are spacers, which don’t ever need to move.

1 Like

Computers without inverters :exploding_head:

1 Like

Additional Papers

I love the overlap between game computing and reversible computation:

Ordinary computers are not reversible. As a result, the information losses that are constantly occurring in an ordinary computer result in an increase in entropy, manifested as heat.