Bitgrid
BitGrid is a low-level programming language.
The runtime is made of cells in a square grid that do computation on a globally synchronized clock. Each cell gets a boolean input from its four rook-neighbors and then sends a boolean output to its four rook-neighbors for the next cycle. Each output is computed by a function of the four inputs using one of the 216 possible four-input boolean functions. The program consists of 64 bits in each grid cell, to determine the four gates each.
The runtime state of BitGrid happens to factorize to two disconnected components in a Crypt of the Necromancer style flashing checkerboard pattern; in the picture to the right, both state components alternate between sending signals from red to blue cells, and from blue to red cells, without ever interacting. We can visualize one component by mapping the corresponding signals to the underlying axis aligned squares. In this view, BitGrid acts by alternating between firing all blue gates (affecting 2×2 bits each) and all red gates (again affecting 2×2 bits each).
BitGrid was invented by Mike Warot between 1981 and 1982.
Computational class
With a finite grid, BitGrid is a finite state automaton.
Note that it is easy to route signals through the gates, including crossovers (where a cell just sends each input to the opposite side as output), as well as implementing standard logical gates, so BitGrid can implement arbitrary circuits.
With an infinite grid, BitGrid is Turing-complete. For example, Nopfunge can be implemented directly. It's also possible to simulate Game of Life or Rule 110.
Game of Life
There are 1616 possible cells. To ease notation we define a few simple ones, where [a, b; c, d] denotes a 2×2 matrix of bits:
Routing
- ' ' maps [a, b; c, d] to [a, b; c, d] — identity
- 'X' maps [a, b; c, d] to [d, c; b, a] — swap opposite bits (cross-over)
- '↓' maps [a, b; c, d] to [a, b; a, b] — copy down (in the 45° rotated view)
- '↑' maps [a, b; c, d] to [c, d; c, d] — copy up
- '→' maps [a, b; c, d] to [a, a; c, c] — copy right
- '←' maps [a, b; c, d] to [b, b; d, d] — copy left
- '⇀' maps [a, b; c, d] to [a, a; c, d] — copy top left to top right
- '↼' maps [a, b; c, d] to [b, b; c, d] — copy top right to top left
- '⇁' maps [a, b; c, d] to [a, b; c, c] — copy bottom left to bottom right
- '↽' maps [a, b; c, d] to [a, b; d, d] — copy bottom right to bottom left
- '⇃' maps [a, b; c, d] to [a, b; a, d] — copy top left to bottom left
- '⇂' maps [a, b; c, d] to [a, b; c, b] — copy top right to bottom right
- '↿' maps [a, b; c, d] to [c, b; c, d] — copy bottom left to top left
- '↾' maps [a, b; c, d] to [a, d; c, d] — copy bottom right to top right
- '↘' maps [a, b; c, d] to [a, b; c, a] — copy top left to bottom right
- '↙' maps [a, b; c, d] to [a, b; b, d] — copy top right to bottom left
- '↗' maps [a, b; c, d] to [a, c; c, d] — copy bottom left to top right
- '↖' maps [a, b; c, d] to [d, b; c, d] — copy bottom right to top left
- '↺' maps [a, b; c, d] to [b, d; a, c] — cycle bits counterclockwise
- '↻' maps [a, b; c, d] to [c, a; d, b] — cycle bits clockwise
- 'Z' maps [a, b; c, d] to [d, a; b, c] — cycle bits: top left → top right → bottom left → bottom right
- 'S' maps [a, b; c, d] to [b, c; d, a] — cycle bits: right right → top left → bottom right → bottom left
- 'N' maps [a, b; c, d] to [c, d; b, a] — cycle bits: bottom left → top left → bottom right → top right
- 'И' maps [a, b; c, d] to [d, c; a, b] — cycle bits: top left → bottom left → top right → bottom right
- '>' maps [a, b; c, d] to [d, b; d, d] — copy bottom right bit to left bits
Logic
- '=' maps [a, b; c, d] to [a, a and c; c, a or c] — sorting network comparator: compute minimum and maximum of left bits, put result in right bits
- '&' maps [a, b; c, d] to [a, a and c; c, a and c] — logical and of left bits
- '|' maps [a, b; c, d] to [a, a or c; c, a or c] — logical or of left bits
- '*' maps [a, b; c, d] to [a, not a and c; c, not a and c] — logical not-and of left bits
Using these cells, we can make a Game of Life Unit Cell of size 26×30 as follows.
X ↾ ⇂ ↼ ↼ ↼ ↼ X X ↺ ↽ ↽ S ↻ ↽ ↽ ↺ X ↺ ↼ N ↖ S ↺ ↙ ↼ ↼ ↺ Z ↖ S ⇃ ↙ ↺ ↘ ↖ ↻ ⇂ ↙ Z ↘ ↼ ↖ ⇃ ↙ ⇁ Z ↘ X ↙ ↗ ↘ ↗ ↘ ↙ ↖ ↙ ↾ ↻ ↘ ↙ X ↽ ↽ ↿ S ↻ ⇁ ↘ ⇂ ↙ ↼ ↼ Z N ↻ N ⇀ N ↘ ↘ ↘ ⇂ ⇁ ⇁ ↖ Z ⇀ ⇀ ⇀ ↘ ↘ ↘ = = = ↖ ↘ ⇁ ↘ ↘ → = = = ↖ ↺ Z ↘ ⇁ ⇁ → = = = = ↖ Z ⇀ ⇀ → → = = = = ⇁ ↻ ↺ ↗ → = = = = → * ↽ ↻ ↽ ↽ ↽ ↗ ↗ → = = = = | X ↼ ↽ ↼ ↼ ↖ ↗ ↗ ↗ = = = = & ↙ ⇃ ↙ ↖ ↗ ↻ ↾ ↾ ⇀ ⇀ ⇀ ↾ ↙ ⇂ ↙ X ↺ ↖ ↖ ↽ ↽ ↽ ← ↺ X ↗ > ↗ ↖ ← ← ← ← ← ↼ ⇃ ↗ ↙ X ↼ ↼ ↼ ↼ ↼ ↖ ↙ ↗ ↙ ↾ ↖ X N ↙ ↿ ↖ ↽ ↽ ↽ ↽ ↽ ↽ ↙ ↖ ↻ ↙ ↾ ↼ ↼ ↼ ↼ ↼ ↼ ↺ ↻ Z X ↼ ↿ ↽ ↽ ↺ ↺ S ↺ ⇀ X X ↾ ⇂ ↼ ↼ ↼ ↼ X
Rule 110
This construction uses a single cell type, axis aligned, mapping t (top), l (left), r (right), and b (bottom) inputs as follows:
- if t is 0, t' = t, l' = r, r' = l, b' = b (swap left and right)
- if t is 1, t' = t, l' = b' = r' = r110(l, b, r)
Example evolution (one state component, with bits being sent towards the colored '+' cells):
0 0 0 0 0 (encoding state ...,a,b,c,d,e,...) 0+0 0+0 0+0 1 0 1 0 1 b b+c c+d d <-- propagates state to the left and right here b 0 c 0 d 0+0 0+0 0+0 <-- note that r110(0,0,0) = 0, so the bottom bits are unchanged 0 0 0 0 0 0 0 0 0 0 (shifted version of ...,a,b,c,d,e,...) 0 0+0 0+0 0 1 0 1 0 1 a+c b+d c+e <-- computes next state here b 0 c 0 d (B = r110(a,b,c), C = r110(b,c,d), ...) 0 0+0 0+0 0 0 0 0 0 0 0 0 0 0 0 (ready for next cycle) 0+0 0+0 0+0 1 0 1 0 1 B B+C C+D D B 0 C 0 D 0+0 0+0 0+0 0 0 0 0 0