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 a < 𝟤𝟢𝟢 line 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).

Read further …

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.

Read further …

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

$\begin{aligned} \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 \end{aligned}$

and observe any sequence’s reconstructibility by dyadic expansion.

Pi. Define $\pi:\{\mathbb{N}\to\mathbb{N}\}\twoheadrightarrow\mathbb{R}$ via

$\begin{aligned} \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 \end{aligned}$

and observe any real’s constructibility by dyadic expansion.

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

Read further …

Posts: 240-238, 237-235, 234-232, 231-229, 228-226, 225-223, 222-220, 219-217, 216-214, 213-211, 210-208, 207-205, 204-202, 201-199, 198-196, 195-193, 192-190, 189-187, 186-184, 183-181, 180-178, 177-175, 174-172, 171-169, 168-166, 165-163, 162-160, 159-157, 156-154, 153-151, 150-148, 147-145, 144-142, 141-139, 138-136, 135-133, 132-130, 129-127, 126-124, 123-121, 120-118, 117-115, 114-112, 111-109, 108-106, 105-103, 102-100, 99-97, 96-94, 93-91, 90-88, 87-85, 84-82, 81-79, 78-76, 75-73, 72-70, 69-67, 66-64, 63-61, 60-58, 57-55, 54-52, 51-49, 48-46, 45-43, 42-40, 39-37, 36-34, 33-31, 30-28, 27-25, 24-22, 21-19, 18-16, 15-13, 12-10, 9-7, 6-4, 3-1

Jonathan Frech's blog; built 2021/02/25 20:27:48 CET