Cellular cir­cuit simulation (#240)

Inspired by grid worlds, non-linear notation and two-di­men­sion­al esolangs, I have attempted to de­sign a few ASCII-art languages myself, none sat­is­fac­to­ry enough for publication. Without the toolchain to interact in a non-typewriter manner — both on the software as well as on the hardware side — paired with the need for an apt en­cod­ing to facilitate higher-order capabilities, I could not manage to create some­thing which stands on its own feet as a proper lan­guage, as opposed to nothing more than a convoluted yet primitive pro­ces­sor emulator.

In the fall of 2020, when I was tasked to teach elementary binary semantics courtesy of a brand new mandatory lecture at my university — constructing half-adders from basic gates and combining them to build full adders —, I thought that exactly this bare-bones grid world might be a fruitful endeavor for constructing and combining gates with a visualization of the entropy’s movement across the cir­cuit (one might foolishly think of a bit meandering across a wire, although this in­ter­pre­ta­tion has no physical merit to it).
Within a few hours, I had managed to settle on a grid world definition together with an under 200 lines long interpreter for it. As I opted for an ASCII-CLI-look — significantly boosting de­vel­op­ment time —, I added image output fa­cil­i­ties for this blog post (for which I swiftly designed a few pixel glyphs; on­ly those used by the grid world), avoiding the need to take screenshots of my terminal emulator.

Source: cellular-cir­cuit-simulation.cpp, building: Makefile
Circuits: cellular-cir­cuit-simulation_adder.cir­cuit, cellular-cir­cuit-simulation_odometer.cir­cuit, cellular-cir­cuit-simulation_spiral.cir­cuit

The grid world

As in most grid worlds, non-inert characters are kept to a minimum: there are two entropy sources 0 and 1, the unary negation gate ! and three binary gates &, | and ^. All oth­er characters except the space allow entropic bits to replicate, the special jumpers < and > allow to cross a gap of three characters, rendering interleaving wires possible.

De­sign­ing a 3-bit adder

-=-

An 𝑛-bit adder performs the com­plete addition of two 𝑛-bit integers, yielding a (𝑛 + 1)-bit integer. It can be realized by chaining 𝑛 full adders, each comprised of two half adders. For the least sig­nif­i­cant bit, the carry in can be assumed to be zero and optimized away, the most sig­nif­i­cant bit’s carry can directly be used as output. As such, the above figure shows - 3 + 3 · 5 = 12 gates, forming a 3-bit adder.

Further circuits

A simpler task than adding two integers is incrementing a single one. This tasks boils down to trickling a singular carry bit, with the least sig­nif­i­cant bit always flipping:

Of course, one can also explore two-di­men­sion­al space without realizing any meaningful com­pu­ta­tion: