Finite Life’s long trajectories

2021-11-27, post № 252

simulation, #cellular-automata

Conway’s Game of Life is classicly played on the infinite two-state grid with only a finite number of cells lit in the starting configuration. Due to its particular rules, Turing machines can be embedded within it, making it equivalently powerful computationally. Paired with the non-existence of a uniform distribution on countably infinite discrete sets, homogenously reasoning about trajetories of all Games of Life is hindered by both an unclear enumeration and fundamental limits of computation.
More tractably, Life can be played on a discrete torus with finitely many states. Because of this global size limitation, Turing completeness is lost since only finitely many world states exist. For host architecture’s compatibility’s sake, I chose to play in an 𝟪 ⨉ 𝟪-sized toric world represented as an uint64_t; with Life’s rules implemented by bit-fiddling. C++20 kindly offers std::pop_count which, paired with bit-wise neighbourhood masks, allows for a clean rule encoding:

const int pc{std::popcount(w & neighbourhood_masks[j])};
if (pc == 3 || (w & (1ULL << j) && pc == 2))
    v |= 1ULL << j;

The corresponding masks are compile-time generated using a constexpr-evaluated lambda returning a std::array<world_t, 64>. Source: fgol-traj.cpp

With finite Life defined and implemented, the question I set out to ask can be posed:

In the finite directed graph of all states with edges representing one time step of evolution according to Life’s rules, one seeks to find world states which either take a long time to fall into a cycle or ones which lead into large cycles. In that regard, this maximum time is an indicator of the ‘entropic depth’ of this simulation.

Since the search space is too vast to be exhaustively searched, the 64 bits which make up a state are pseudo-randomly uniformly chosen and evolved. Keeping track of previously simulated initial state’s times, a record is kept. As of now, the longest trajectory length has been 401, achieved by the following starting configuration:

$ ./fgol-traj 0558cdc8400d3b35
world 0558cdc8400d3b35:
[]  []  [][]    
[][]  [][][]    
[]  [][]        
            []  
      []    [][]
[]  [][]    [][]
      [][]  []  
[]  []          

trajectory length until first self-colision: 401
periodicity: 132
first point of periodicity: 0000c0b070000000

Before this trajetory length, two states were found with a score of 375: 8e423847408ec519 and 94c0f9892ad05be8.

Yet this method only achieves lower bounds. Starting states which take longer than 300 steps to repeat already seem to be quite rare; finding the above state took multiple hours of searching. And because of this problem’s highly non-continuous nature, a rogue state could be lurking out there in the vastness of thought, waiting to be discovered by someone.

Halloween MMXXI: Uncanny Woods

2021-10-31, post № 251

prose, #halloween

Treading muddied woodland grounds, a squeak did interrupt my slumber: for that I knew I was alone, amidst the grayish silhouettes ahead of me, a dim cinder I could witness. For it was only briefly lit, I felt its simmering prolonged. A frosty gust of air firmly held me grasped in place: a shuffling in the branches sent blockage swiftly my way. I dare not dream a moment shifted, was forced to alter all my venture. It had been long from when I hurried, it would be long to when I rest. Marching ment moving, a certain goal. But arrival was not certain, the path now winded and uncharted. What was it that has led me here, what did I seek, what wish to find? It could be that it was quite near, or ever further gone the more I hoped to clench it tight.
Canopies lifting everso slightly, my future forking akin to the countless branches left behind: should I continue forward, sloping down and narrowed, or should I turn and head on sideways, this path more open though it may be longer? A twig fell down, to guide me it seemed. I wedged my feeble body through the thicking foliage. Slowed down by ever denser flora, drained and worn I stopped. I stood. I listened to the world around me. I slumbered.
Close off my entrance the woodlands did. For I was drowsy, forwards slipped my mind. Where to now? — Another spark. The last remnants of hope mounting, I stepped, misstepped. Leafy branches swept over. The forest rested.

The humble sum should neither necessitate indirection nor be unbounded across package boundaries

2021-10-30, post № 250

language-design, #go

Routinely, I am irked by the effort required in most languages to express algebraic data types — the epitome of information itself. An inert datum is too often occluded by hardware-inspired lingo forcing one to adapt to rigid register-fitted types. Leastways the C lineage supports bytestrings together with their concatenation which, under the previous constraints, are equatable to product types. Though whilst control flow neatly factors through such a type, the categorical dual consistently requires an iffy cast or virtual semantics alltogether: the humble sum is quietly ignored in favor of its dual in whose hulking shadow it sometimes desintegrates out of existence. A far cry from Haskell’s effortless type alternative “|”, C at least supports byte-based type superpositioning. Yet although Go inherits “struct”, the fameless yet in no way inferior “union” is — to me unreasonably — absent.

Consequently, when I implemented miniKanren in Go back in March of 2021^[1], I was flabber­gasted to find a gaping language definition hole where I had expected a sum type. Toying with the idea to one-hot encode S-expressions via

I quickly dismissed it in hopes of a more elegant idiomatic Go approach. What I found was an interpretation of a sum type which conflates object action, dynamic dispatch, undefined control flow and unbounded sums into a briddle mess of Go lines which can be viewed as indeed implementing a type coproduct. Needless to say, I am dissatisfied with Go’s negligence in this regard.

Hoisting HTTP headers home

2021-10-02, post № 249

web, #http, #header

While developing my new minimalistic HTTP backend — a web server called vanadium —, scourering MDN’s HTTP header documentation and inspecting the headers sent by web servers serving public websites, I first stumbled upon the header “Server” and decided for my server to tell the world its name. Yet most servers send a lot of headers, many of which non-standard and most of unclear purpose to myself. This discovery made me think: HTTP headers may be the most commonly sent textual data virtually invisible to most computer operators due to common web browser’s failure to communicate them. Thus I will in this post shine a light on my findings examining various web server’s initial banter.

Interrogation of web servers hinges on using a capable client, as without the server’s headers, no web browser could fulfill its role as a HTTP client. Yet this communication is often hidden from the user. One client which allows viewing headers is curl, although one has to read its man page thoroughly:

$ curl -fsSLD- -o/dev/null https://...

Above, curl is invoked to fail silently, be silent about its network progress yet still Show errors, follow Location redirects and Dump the HTTP response header to standard output (indicated by a singular dash). Furthermore, the response’s body is output to the null device.
Note that web servers may respond differently to different user agents, about which intel is acquired via the HTTP header “User-Agent” sent by the connecting client. One may specifically remove or set this header using $ curl -A '' or the same with a non-empty flag argument. Since I did neither, curl sent its own name together with its version, for me “curl/7.77.0” and “curl/7.74.0”.

Amusing HTTP headers

Looking at the sometimes dozens of headers sent by various websites, among the cookies and entity tags one finds sparsely sprinkled innocent items of information. Heise for one, a German publishing house operating “heise.de” and “ct.de”, configured some of their Apache and nginx servers to spew a whopping four non-standard inert HTTP headers at unsuspecting surfers:

$ curl -fsSLD- -o/dev/null heise.de | grep ^X
X-Cobbler: servo65.heise.de
X-Pect: The Spanish Inquisition
X-Clacks-Overhead: GNU Terry Pratchett
X-42: DON'T PANIC

Compiling to native brainfuck

2021-09-04, post № 248

programming, #brainfuck, #compiler, #antibloat

Esoteric languages explore novel approaches to computing. Whilst the vast majority of traditional languages decend from C-style von Neumann architecture commandments, these language’s notation and approach to data processing is by design and identity different. Yet in contrast to golfing languages, graphical languages or the even more esoterically inclined, brainfuck can be thought of as a supremely distilled imperative instruction set rather than an unknown beast entirely. Furthermore, its Unix-like approach to I/O makes it suitable to truly use as a target instruction set as the isomorphism behind its Turing completeness is not as opaque as in other esolangs. However, with its minimalistic nature comes questionable performance and tedious development overhead. Thus, a lot of brainfuck programs found in the wild are mere Kolmogorov complexity solutions, taking no input and being optimized to tersely output a constant string of bytes. Nevertheless, writing non-Kolmogorov programs by hand is possible as I have shown in e. g. Interpreting brainfuck in C.
To be able to write more complex programs and compile them to native brainfuck, I have been working since late 2018 on an abstraction concept and implementation thereof. Interest faded inexplicably around Christmas of 2019 such that I only now — one an a half years later — polished my Brainfuck Compiler Project to the point of readiness for unveiling. Notably, it has already been used without mention in Generating the Prouhet-Thue-Morse sequence in brainfuck.

At its core lie two means of abstraction: firstly, the raw tape is symbolically named and scoped via the Tape Abstraction Language which secondly gets extended to a Macro Assembler complete with a basic usage-oriented cell type system and natural derivation capabilities. After all macros are expanded, the residue is compiled to brainfuck. For execution purposes, said brainfuck code is transpiled to C and compiled to a binary using an off-the-shelve C compiler. The result is a fairly readable LISP-inspired macro language which compiles down to machine-executable brainfuck.

Brainfuck Compiler Project is truly free software in the moral interpretation. All project files are bundled in a single tarball: 2021-09-04_jonathan-frech_brainfuck-compiler-project.tar^[1]. For ease of use I wrote a shell script which downloads said tarball, installs it temporarily and runs it on a given source file: run.sh

Early Tape Abstraction Language drafting.

Plant fibre puppet

2021-08-07, post № 247

poetry, art, #dialogue, #drawing

              |         such
zuch          |             
              |    thus such
thuz zuch     |             
              |  seldom such
zeldom zuch   |             
              |         such
zuch          |             
              |         such
zuch          |             
              |           so
zo            |             
              |            .
nah           |             
zuch-zeldom-  |             
  zuch-zuch   |             
nah           |             
              |      similar
zimilar       |             
              |            .
nah           |             
zeldom-zuch-  |             
  zimilar-    |             
  zuch-zuch   |             
nah           |             
              |          ...
...           |             
              |         nah.
! zrk-rr r    |             

Factoids #3

2021-07-10, post № 246

mathematics, #topology, #reals, #lipschitzian

X) An intriguingly delicate arbitrarily small countable open cover of uncountably many unbounded points inferred from locally lipschitzian maps’ inability to increase a set’s Hausdorff dimension

Claim. For any uncountable Lebesgue measure zero set , there exists a point such that is still uncountably infinite. Define and on this right portion as . Looking at the graph , it is a Hausdorff measure zero set — meaning the entirety of all uncountably many points clustered at span an infinite vertical distance and yet are coverable by countably many sets of arbitrarily small diameter in sum.

Proof. Since is locally lipschitzian and the reals are Lebesgue -compact, its image cannot increase the one-dimensional Hausdorff measure which is presumed to vanish.

Solving peg solitaire by pure chance

2021-06-12, post № 245

C, #board-game

In all the years I regularly glanced at our peg solitaire on the board game shelf, seldomly even playing it and attempting a solve — moving 31 out of the total 32 pegs such that the final peg ends up at the board’s center —, yet never succeeded. The closest I got always left two or three pegs standing far between each other, calling doom for my solve.

One lobe cleared.

Not being able to solve this game, the other day I had the idea of pseudo-random game space exploration, my optimism driven by both the moderate number of pegs as well as the strict monotonicity of the game leading to all solutions being of the same length and thus in a sense equal — bearing in mind consecutive hops in the same direction are not considered as a singular move.