Cellular circuit simulation

2021-02-20, post № 240

c++, grid-world, #binary, #logic, #gate, #ppm

Inspired by grid worlds, non-linear notation and two-dimensional esolangs, I have attempted to design a few ASCII-art languages myself, none satisfactory 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 encoding to facilitate higher-order capabilities, I could not manage to create something which stands on its own feet as a proper language, as opposed to nothing more than a convoluted yet primitive processor 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 circuit (one might foolishly think of a bit meandering across a wire, although this interpretation 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 development time —, I added image output facilities for this blog post (for which I swiftly designed a few pixel glyphs; only those used by the grid world), avoiding the need to take screenshots of my terminal emulator.

Source: cellular-circuit-simulation.cpp, building: Makefile
Circuits: cellular-circuit-simulation_adder.circuit, cellular-circuit-simulation_odometer.circuit, cellular-circuit-simulation_spiral.circuit

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 other 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.

Designing a 𝟥-bit adder

Calculating 0b110 + 0b011 == 0b1001 using a 𝟥-bit adder (input bits are interleaved, less significant bits reside on the left).

Visualizing cycles in row-major transposition encodings

2021-01-23, post № 239

mathematics, programming, c++, shell, #matrix, #encoding, #permutation, #rainbow

A matrix A\in \mathcal{D}^{h\times w} of discretely representable entries \mathcal{D} may be linearly layed out in memory using row-major order, concatenating successive rows into a contiguous (h\cdot w \cdot\texttt{sizeof}\,\mathcal{D})-bytes long array. Such a representation, however, is disruptive to the matrix’ two-dimensional nature: whilst horizontally neighboring elements remain neighbors, vertically neighboring entries are torn apart by insertion of w non-neighboring elements. As such, on matrices naturally defined operations get distorted by this encoding.
One such inherently two-dimensional operation is matrix transposition. In the realm of matrices, \mathcal{D}^{h\times w}\neq\mathcal{D}^{w\times h} are for nonsquare dimensions semantically different, being mapped to one another by transposition. Projecting onto their encoding, this semantic is lost and one is left with a permutation on memory \bullet^\top\in\mathrm{Sym}(\{1,\dots,hw\}).
To visualize this permutation, its cycle decomposition is computed of which each cycle is given a color of the rainbow dyeing this cycle’s corresponding two-dimensional pixels when interpreting its path on the underlying array in the semantics of the original matrix.

Initial transposition cycles

Above listed are all visualizations for 1\leq h\leq 8,1\leq w\leq 16, shuffled. Whilst some behave extremely regularly — for example square matrices’ transposition permutations decompose into transpositions —, others are wildly intricate. Each of them adheres to a rotational symmetry; the top left and bottom right are fixed points.

Factoids #2

2020-12-26, post № 238

mathematics, #bijection, #calculus, #Lipschitz, #naturals

VII) Cardinality coercion: \mathbb{R}\hookleftarrow\{\mathbb{N}\to\mathbb{N}\}\twoheadrightarrow\mathbb{R}

Claim. There exist both \iota:\{\mathbb{N}\to\mathbb{N}\}\hookrightarrow\mathbb{R} together with \pi:\{\mathbb{N}\to\mathbb{N}\}\twoheadrightarrow\mathbb{R}.
Proof. Iota. Define \iota:\{\mathbb{N}\to\mathbb{N}\}\hookrightarrow\mathbb{R} via
    \iota(a):=\quad&\sum_{j=1}^\infty 2^{\left(1-\sum_{i=1}^{j}(1+a(i))\right)}\cdot(2^{a(j)}-1)\\
    =\quad&\left(0.\underbrace{1111\dots11}_{\times a(1)}0\underbrace{111\dots11111}_{\times a(2)}0\dots\right)_2
and observe any sequence’s reconstructibility by dyadic expansion.
Pi. Define \pi:\{\mathbb{N}\to\mathbb{N}\}\twoheadrightarrow\mathbb{R} via
    \pi(a):=\quad&a(1)+\sum_{j=2}^\infty 2^{1-j}\cdot\delta_{a(j)\in 2\mathbb{Z}}\\
    =\quad&a(1)+\left(0.\delta_{a(2)\in 2\mathbb{Z}}\delta_{a(3)\in 2\mathbb{Z}}\delta_{a(4)\in 2\mathbb{Z}}\dots\right)_2
and observe any real’s constructibility by dyadic expansion.

Thus, \{\mathbb{N}\to\mathbb{N}\}\cong\mathbb{R} in \mathbf{(SET)} is shown.

Jonathan Frech's blog; built 2021/04/16 21:21:49 CEST