Arvi Teikari’s discrete self-referencing puzzler has fascinated with its non-formulaic take on box pushing since its early days as a contest entry in April of 2017 [1]. Whilst its vanilla level set is vast, conceptually coupled as well as thematically aligned, one cannot expect it to exhaustively cover the gargantuan space of world scenarios, even after filtration by solvability and playfulness.
As such, in line with the ever increasing shift in gaming away from the ROM-baked whollistic experiences towards providing loose game-inducing boundaries on internet-driven platforms — dually tending to the consuming player as well as the niche creator in one —, of particular note being Roblox, LittleBigPlanet, Super Mario Maker, its sequel and Dreams, it was a natural step for Teikari to open up their game to become a puzzler engine in late 2020 [2], allowing anyone to tinker with the shifting ways of their visually dissonant purely property-induced worlds.
For approaching a third of my time on this earth, I have been blogging about my projects, my findings, my poetry, my systems. Looking back on it, reminiscing in distaste about the humble beginnings of graphically oriented slow snake scripting to dubious groking of Unix and numerics, meandering through games neither played nor parodied and taking my first swings at golfing. Dabbling in pixel painting, moving away from imprisoned evaluating. Graduating. Experiencing symbolicism, doubting the physicist’s model’s realism. Writing compilers, construeing languages, calculating Laplacians. Discovering sequences and trails of old — in thought and *ware. Hopping by the GNUs of new, making sense of the legacy that is Berners-Lee’s. Wrestling with what once was freedom. Writing a Bachelor’s thesis. Tasting concurrency, rediscovering simplicity. Loathing light in captured form. Lonely for the depths are known.
Looking back, I am unsure if it was worth it. I sometimes dream to have been born a Unix pioneer, not hindered by the mischief caused by modern datum’s drought for thought. Yet then again — romantically —, glorifying the past immensely, doubt creeps in if in all honesty, life’s discretization is after all not robbery. For should I not be content pondering what is constructed and then wondering why I am yearning for the improbable that is acceptance of the unloggable?
I detest conducted computing. I believe in free software. I think open source is an unjust blanket. I wish to seek asylum in the analogue. I am writing this on my Thinkpad X250 running proprietary WiFi drivers in an editor whose benevolent license I despise. The birds are tweeting.
Ever since watching D. Knuth’s talk “Tchoukaillon numbers” [1] in the Rutgers experimental mathematics seminar back in January of 2022, I was intrigued by the algorithm he presented to iteratively generate the Tchoukaillon arrays ꚓ⁽ⁿ⁾. Their discrete pointwise limit defines a two-dimensional permutation of the natural numbers, whereby pointwise exactly one value is attained more than once. These properties make calculating the discrete limit expressible as a lazy computation:
tcheInf i j = discreteLimit $ \n -> tche n i j
Despite the seeming simplicity of iteratively taking hooks from an -matrix, two-dimensional problems seem to require extra scrutiny when approached with a linear data model, even more so without arbitrary jumps. To not transpose too often — thereby invalidating the previous computations’ linearity — I took the approach of linearly evaluating a micro-DSL to express each finitely wide tche n as finite chunks of tcheFlat n :: [Int]:
tcheFlat 1 = [1..]
tcheFlat n = eval (cycle actions) $ tcheFlat (n-1) where
actions = concat [[flat (n-m), grab (n-m-1,m)] | m <- [1..n-1]]
tche n i j | j <= n = (chunksOf n $ tcheFlat n) ## i ## j
| otherwise = -n
Of course left in the dust by the closed-form formula, D. Knuth’s table’s corner element is computationally viably accessible using this method:
Without the intend to trivialize the world of material possessions, possibly the novelty alone makes the many quirks and unseen effects which occur in the presence of information-centric conduct hard to grasp in its entirety. Most bizarrely, the concept of ownership admits only to a loose analogy: expected algorithmic runtimes to reproduce bit patterns. Yet if these expections are broken or systems otherwise circumvented, stolen goods are merely accurately replicated hunks of data; nothing ever gets moved or removed, only copied against the origin’s will. Still, the significance is akin to theft, only securing bits requires more than not losing them.
As such, it is no wonder that a tender technology like the web took a long and winded path before reaching present-day hardened cryptographic ubiquity. But the tolls of time and progress are plentiful: from the fundamentally inextensible to the obsolete and the undying facets kept alive through compatibility shims, one of such shims being HTTP-talking sockets whose only assignment is to appeal to the client’s senses and never to talk with them again, referring to their HTTPS comrades which are in control of the sought after pages. Yet cannot the clients remember? Should the clients even seek port 80? What does it mean to support SSL? To enforce it? Answers to these questions are given by HSTS, yet it too has morphed over the years; and a server’s adherence is not certain.
Inheritance is all about keeping material possessions in the familly. Thus, a child may access non-private parent members:
#include <iostream>
struct A { int v{5}; };
struct B : A {
void f() { std::cout << v << std::endl; } };
int main() { B{}.f(); }
Even though v has not been declared inside struct B’s declaration, it accesses it through its inheritance ties to struct A. Feeling the need to be polymorphic with regards to the numerical representation, struct A may be changed to a struct template:
#include <iostream>
template<typename T> struct A { T v{5}; };
struct B : A<int> {
void f() { std::cout << v << std::endl; } };
int main() { B{}.f(); }
Yet hard-baking in the numerical type for the derived struct feels overly restrictive. As such, one might want to build a templated class hierarchy:
#include <iostream>
template<typename T> struct A { T v{5}; };
template<typename T> struct B : A<T> {
void f() { std::cout << v << std::endl; } };
int main() { B<int>{}.f(); }
What surprised me nearly two weeks ago — when a templated class hierarchy naturally arose — is that the above does not compile.
$ clang++ 2.cpp
2.cpp:4:29: error: use of undeclared identifier 'v'
void f() { std::cout << v << std::endl; } };
^
1 error generated.
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:
For how long can one play finite Life until revisiting a world state?
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.
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.
-matrix, two-dimensional problems seem to require extra scrutiny when approached with a linear data model, even more so without arbitrary jumps. To not transpose too often — thereby invalidating the previous computations’ linearity — I took the approach of linearly evaluating a micro-DSL to express each finitely wide 
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.
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.