12 Five sets and time
(ns meme-constructor.posts.post-03-five-sets-and-time
(:require [scicloj.kindly.v4.kind :as kind]
[clojure.set :as set]
[meme-constructor.generators :as g]
[meme-constructor.reach :as r]
[meme-constructor.figures :as fig]))Post 3 of Part II, “Memes as Abstract Constructors”.
What a host can reach and how fast it gets there are separate questions, and efficiency lives in the second. Two hosts with the same step relation reach the same memes in the same number of steps, yet one finds its targets twenty times faster, because it searches better. The reachable sets do not separate open from closed hosts either: whether they saturate follows the size of the behaviour space, and fast growth needs steps that combine ideas, which closed grammars have too.
The sets are De la Guardia’s (2025a) five nested sets. This post defines them on the host model of post 2 (Definition 2.1), with the step relations of post I.1, and counts them in two toy generators. \(T(s)\) is the repertoire of state \(s\), and \(s\) carries meme \(m\) iff \(T_m \subseteq T(s)\) (post 1, Definitions 1.6 and 1.7).
12.1 1. The five nested sets (F4)
In De la Guardia’s words: Active is “the set of things currently active in the mind”, Existing “all the knowledge in the mind”, N-Reachable what “you don’t yet have, but might reach in N steps”, ω-Reachable “all the things you can ever reach, given unlimited time and resources”, and Possible “all the things that are possible in reality”. Everything depends on what a step is.
Definition 3.1 (Step relation). The step relation of a host \(H\) is one input write followed by one own step (post I.1, Definition I.1.3):
\[s \leadsto_H s' \iff \exists\, u:\ s \leadsto_{\mathrm{in}} u \leadsto_S s' .\]
It includes perception: what the host sees may steer its next step. It excludes programming: nothing outside installs a pattern. A host that is taught still learns by its own steps, with the teaching as input. In the toy generators below a step is one edit of the carried program, and any edit may be the next one.
Definition 3.2 (Five sets, state level). With \(s_0\) the current state and \(\leadsto_H^{\le N}\) reachability in at most \(N\) steps,
\[\{s_0\} \subseteq \mathrm{Reach}^S_N = \{ s \mid s_0 \leadsto_H^{\le N} s \} \subseteq \mathrm{Reach}^S_\omega = \bigcup_N \mathrm{Reach}^S_N \subseteq S .\]
Because \(\leadsto_H\) allows every input, \(\mathrm{Reach}^S_\omega\) is the ω-Reachable with outside input. Post I.2 keeps it apart from what a system reaches with nobody feeding it, which is what self-reachability (C3) asks about. Here the difference matters little: every host below is fed its evidence as input.
Definition 3.3 (Five sets, meme level). Let \(M(s)\) be the memes \(s\) carries. Then
\[\begin{aligned} \text{Existing} &= M(s_0), \\ \text{N-Reachable} &= \bigcup \{ M(s) \mid s \in \mathrm{Reach}^S_N \}, \end{aligned}\]
and ω-Reachable likewise. Active is a designated subset of Existing. Possible is the set of memes \(m\) for which “bring some substrate into a state that carries \(m\)” is a possible task in the constructor-theoretic sense (post 1, Definition 1.2), whether or not \(H\) can do it.
The inclusions Active ⊆ Existing ⊆ N-Reachable ⊆ (N+1)-Reachable ⊆ ω-Reachable ⊆ \(M(S)\) hold by definition, once N-Reachable is read to include Existing. \(M(S)\), what \(H\)’s hardware could carry, is a sixth set between ω-Reachable and Possible. That \(M(S) \subseteq\) Possible is not a matter of definitions. In the toys it holds by stipulation. Possible is taken in the physical sense so that it does not depend on \(H\). Memes can then be compared across substrates because information is interoperable (Deutsch & Marletto 2015).
The sets are defined on states and mapped to memes, not built from a step relation on memes. One could say \(m \leadsto m'\) if some state that carries \(m\) steps to some state that carries \(m'\). That overcounts, because a host holds one particular state, not every state with the same behaviour. [:rep 2 :grasp] and [:seq :grasp :grasp] in the closed generator of post 2’s library behave alike, but their one-step successors differ:
(def closed-small (assoc g/closed-generator :max-size 5))(let [sigs (fn [m] (set (map #(r/signature closed-small %) (g/successors closed-small m))))
a (sigs [:rep 2 :grasp])
b (sigs [:seq :grasp :grasp])]
{:same-behaviour? (= (g/repertoire [:rep 2 :grasp]) (g/repertoire [:seq :grasp :grasp]))
:behaviours-one-step-from-rep (count a)
:behaviours-one-step-from-seq (count b)
:shared (count (set/intersection a b))}){:same-behaviour? true,
:behaviours-one-step-from-rep 101,
:behaviours-one-step-from-seq 131,
:shared 56}Observation 3.4 (no seed). Same behaviour, but one step reaches 101 behaviours from the first and 131 from the second, only 56 of them shared. In the code below, “memes” counts syntactic states and “behaviours” counts their images.
12.1.1 1.1 Independent of Existing: persistence
De la Guardia’s ω-Reachable is meant to be “independent of Existing”: what a mind can ever reach should not depend on what it happens to hold now. The precise form is post I.2’s persistence, read for memes.
Definition 3.5 (Persistent ω-Reachable). ω-Reachable is persistent at \(s_0\) if no step loses any of it:
\[\omega\text{-Reachable}(s) = \omega\text{-Reachable}(s_0) \quad \text{for every } s \in \mathrm{Reach}^S_\omega(s_0) .\]
Proposition 3.6 (Persistence from strong connectivity). Let \(U \subseteq S\) be closed under \(\leadsto_H\) and strongly connected: every \(u \in U\) reaches every \(u' \in U\). Then \(\mathrm{Reach}^S_\omega(s_0) = U\) for every \(s_0 \in U\), and ω-Reachable is persistent at every state of \(U\).
Proof. \(\supseteq\) by strong connectivity, \(\subseteq\) by closure. Every state reachable from \(s_0\) lies in \(U\), so it has the same state-level set, hence the same meme-level set. \(\square\)
Strong connectivity is sufficient, not necessary. It asks that every step can be undone. Persistence asks only that no step loses a meme from reach. A dovetailer, one of the enumerators of post I.2, never repeats a state, so it is not strongly connected, yet every program stays ahead of it. Both toy generators are strongly connected within their size bounds, since each edit can be undone by other edits. We check it for the closed one against a direct enumeration of all derivations with at most 5 nodes:
(def closed-universe (r/all-trees 5))(defn closure [gen init]
(apply set/union (:layers (g/reachable gen init 30))))(let [a (closure closed-small :grasp)
b (closure closed-small [:rep 3 :lick])]
{:universe (count closed-universe)
:from-grasp (count a)
:equal? (= a b (set closed-universe))}){:universe 11562, :from-grasp 11562, :equal? true}Observation 3.7 (no seed). From :grasp and from [:rep 3 :lick] the closed generator reaches the same 11,562 derivations, all of them. The tests check the same for counter machines of length at most 2. A host whose learning entrenches some memes, so that others drop out of reach, would not be persistent.
12.2 2. Reachable sets do not separate open from closed
One might think that N-Reachable runs into a fixed bound and saturates in a closed host, while in an open host “every new concept is a new axis” and N-Reachable grows faster than linearly in the number of concepts. We test it on two generators from post 2’s library: a closed context-free grammar of behaviour programs, and counter machines, which are universal. It does not hold, and one part of the answer needs no computing.
Definition 3.8 (Unary and combining steps). A step is unary if it edits one carried meme and does not depend on the others, as in g/successors. A combining step takes two carried memes \(a, b\) to their sequential composition “do \(a\), then \(b\)”: [:seq a b] in the grammar, and for counter machines \(a\) with its halts redirected to the start of \(b\) (r/compose).
Proposition 3.9 (Unary steps are subadditive). If every step is unary, then
\[\begin{aligned} \text{N-Reachable}(E) &= \bigcup_{m \in E} \text{N-Reachable}(\{m\}) , \\ |\text{N-Reachable}(E)| &\le |E| \cdot \max_{m \in E} |\text{N-Reachable}(\{m\})| . \end{aligned}\]
Proof. Each step acts on one meme, so following a path back leads to one \(m \in E\). Images preserve unions. \(\square\)
So no generator with unary steps grows faster than linearly in the number of concepts, open or closed. “Every concept is a new axis” needs combining steps, and a closed grammar can have them.
12.2.1 2.1 Growth in N
|N-Reachable| against N from one meme, with size bounds tight enough to enumerate the whole universe. Closed: at most 5 nodes. Open: 2 registers, at most 3 instructions. The open behaviour signature is the output on inputs 0 to 7 within 100 steps, a finite stand-in, since exact behavioural equality is undecidable (post 2).
(def open-small {:kind :counter-machine :registers 2 :max-length 3
:budget 100 :probe-inputs (vec (range 8))})(def n-closed (:rows (r/n-reach-rows closed-small :grasp 7 {})))(def n-open (:rows (r/n-reach-rows open-small [[:halt]] 4 {}))){:closed n-closed
:open n-open
:open-universe {:memes (count (r/all-programs 2 3))
:behaviours (r/count-behaviours open-small (r/all-programs 2 3))}
:closed-universe {:memes (count closed-universe)
:behaviours (r/count-behaviours closed-small closed-universe)}}{:closed
[{:n 0, :memes 1, :behaviours 1}
{:n 1, :memes 52, :behaviours 48}
{:n 2, :memes 3342, :behaviours 2263}
{:n 3, :memes 9026, :behaviours 5893}
{:n 4, :memes 11482, :behaviours 7733}
{:n 5, :memes 11562, :behaviours 7758}
{:n 6, :memes 11562, :behaviours 7758}
{:n 7, :memes 11562, :behaviours 7758}],
:open
[{:n 0, :memes 1, :behaviours 1}
{:n 1, :memes 62, :behaviours 5}
{:n 2, :memes 4791, :behaviours 20}
{:n 3, :memes 69495, :behaviours 101}
{:n 4, :memes 69559, :behaviours 101}],
:open-universe {:memes 69559, :behaviours 101},
:closed-universe {:memes 11562, :behaviours 7758}}(def colors ["#2a78d6" "#eb6834" "#1baf7a" "#eda100"])(defn trace [rows xk yk nm c dash]
{:type "scatter" :mode "lines+markers" :name nm
:x (map xk rows) :y (map yk rows)
:line {:width 2 :color c :dash dash} :marker {:size 7 :color c}})(kind/plotly
{:data [(trace n-closed :n :memes "closed, memes" (colors 0) "dot")
(trace n-closed :n :behaviours "closed, behaviours" (colors 0) "solid")
(trace n-open :n :memes "open, memes" (colors 1) "dot")
(trace n-open :n :behaviours "open, behaviours" (colors 1) "solid")]
:layout {:title {:text "|N-Reachable| from one meme, tight size bounds"}
:xaxis {:title {:text "N (steps)"} :dtick 1}
:yaxis {:title {:text "count (log scale)"} :type "log"}
:legend {:orientation "h" :y -0.25}
:margin {:t 50 :r 20}}})Observation 3.10 (no seed). Both generators saturate, at their bounded universes. The closed one reaches all 11,562 derivations (7,758 behaviours) by N = 5. The open one reaches all but 64 of its 69,559 programs by N = 3 and all by N = 4, and they carry only 101 distinct behaviours. So saturation in N follows the size bound, not closedness. Without a bound both counts grow for ever: a context-free grammar is not universal and still has infinitely many behaviours.
12.2.2 2.2 Growth in the number of concepts
Existing holds the first \(k\) memes of a seeded list, for \(k = 1, 2, 4, \ldots, 128\). We count 1-Reachable(Existing) with and without the combining step. The bounds are loose (40 nodes, 30 instructions), so they do not cap the compositions.
(def closed-large (assoc g/closed-generator :max-size 40))(def open-large (assoc open-small :max-length 30))(def ks [1 2 4 8 16 32 64 128])(def closed-memes (r/random-memes closed-large 1 128 {:meme-size 4}))(def open-memes (r/random-memes open-large 1 128 {:meme-length 3}))(def sweep
(into {} (for [[nm gen ms] [[:closed closed-large closed-memes] [:open open-large open-memes]]
comb [false true]]
[[nm comb] (r/existing-sweep gen ms ks {:combine? comb})])))(kind/plotly
{:data [(trace (sweep [:closed false]) :k :behaviours "closed, unary" (colors 0) "dot")
(trace (sweep [:closed true]) :k :behaviours "closed, combining" (colors 0) "solid")
(trace (sweep [:open false]) :k :behaviours "open, unary" (colors 1) "dot")
(trace (sweep [:open true]) :k :behaviours "open, combining" (colors 1) "solid")
{:type "scatter" :mode "lines" :name "slope 1 (linear)"
:x ks :y (map #(* 48 %) ks) :line {:width 1 :color "#888888" :dash "dash"}}]
:layout {:title {:text "Distinct behaviours in 1-Reachable(Existing) (seed 1)"}
:xaxis {:title {:text "memes in Existing, k (log scale)"} :type "log"}
:yaxis {:title {:text "distinct behaviours (log scale)"} :type "log"}
:legend {:orientation "h" :y -0.25}
:margin {:t 50 :r 20}}})The counts at \(k = 128\), and the local growth exponent between \(k = 64\) and \(k = 128\), where 1.0 means linear:
(kind/table
(for [[[nm comb] rows] (sort-by (comp str key) sweep)
:let [row (last rows)]]
{:host nm :combining? comb :k (:k row) :memes (:memes row) :behaviours (:behaviours row)}))| host | combining? | k | memes | behaviours |
|---|---|---|---|---|
| closed | false | 128 | 17375 | 12817 |
| closed | true | 128 | 32073 | 23772 |
| open | false | 128 | 27664 | 80 |
| open | true | 128 | 42146 | 111 |
(into {} (for [[key rows] sweep]
(let [{a 64 b 128} (into {} (map (juxt :k identity)) rows)]
[key {:memes (/ (Math/log (/ (:memes b) (double (:memes a)))) (Math/log 2))
:behaviours (/ (Math/log (/ (:behaviours b) (double (:behaviours a)))) (Math/log 2))}]))){[:closed false]
{:memes 0.9552813343536477, :behaviours 0.9093690665366512},
[:closed true]
{:memes 1.3819974072567547, :behaviours 1.3369966579947434},
[:open false]
{:memes 1.0353710013420796, :behaviours 0.4150374992788437},
[:open true]
{:memes 1.3306318271558906, :behaviours 0.5464883529065205}}Observation 3.11 (seed 1). Counted by syntax, both generators grow, and the open one faster: with the combining step and \(k = 128\) it reaches about 42,000 programs against about 32,000 derivations. Counted by behaviour, the picture reverses. The closed generator reaches about 24,000 distinct behaviours, the open one about a hundred. With unary steps both grow sublinearly, as Proposition 3.9 requires. With the combining step the closed generator grows faster than linearly (local exponent about 1.3), and the open one does not.
So the prediction fails in the model, for reasons of which only the last is specific to the toy.
12.3 3. Same reachable sets, different speed (F5)
“Quickly” needs a clock. Deutsch & Marletto (2025, §5–6) define a timer as an isolated constructor that shows “running” until it shows “done”, and a task is done in time \(t\) if it completes while a timer of duration \(t\) runs. Applying this to what a host constructs is our extension. Post I.1 builds a timer as a Push program in a state of its own (Definition I.1.10). Under a fixed schedule its reading is a count of the host’s steps, so here one tick is one candidate the host’s search examines, kept outside the host’s step relation so that the host cannot change what a tick is.
Definition 3.12 (t-Reachable). A meme \(m\) is in t-Reachable\((H)\) if \(H\), from its current state and given its evidence as input, comes to carry \(m\) before a timer of duration \(t\) shows done.
t-Reachable is defined on states and projected to memes, like the five sets, because speed is not a property of an abstract constructor: members of one class can differ about thirtyfold in time (post I.1, Proposition I.1.12). It grows with \(t\).
Two tempting links between steps and time fail. Both hold only for a host that is told which path to take.
Two hosts share the closed generator with at most 5 nodes, so they have the same step relation, the same N-Reachable for every N, and the same ω-Reachable (Observation 3.7). Both start from Existing \(= \{\):grasp\(\}\) and are shown a target behaviour, the evidence of a copy task. Host A searches breadth-first and uses the target only to recognise success. Host B searches greedily: it always expands the candidate whose behaviour is closest to the target, measured as the summed edit distance of the action sequences. The targets are 30 seeded random derivations.
(def bfs-times (r/bfs-times closed-small #{:grasp} 20000))(def targets (mapv #(r/signature closed-small %) (r/random-memes closed-small 7 30 {:meme-size 5})))(def times-a (mapv bfs-times targets))(def times-b (mapv #(r/guided-time closed-small #{:grasp} % 20000) targets))(defn median [xs] (let [v (vec (sort xs))] (v (quot (count v) 2)))){:behaviours-covered-by-A (count bfs-times)
:last-first-reach-A (apply max (vals bfs-times))
:median-A (median times-a) :max-A (apply max times-a)
:median-B (median times-b) :max-B (apply max times-b)
:B-faster (count (filter true? (map < times-b times-a)))
:B-slower (count (filter true? (map > times-b times-a)))}{:behaviours-covered-by-A 7758,
:last-first-reach-A 11561,
:median-A 2817,
:max-A 10802,
:median-B 133,
:max-B 751,
:B-faster 22,
:B-slower 0}(def ts (vec (range 0 12001 50)))(kind/plotly
{:data [{:type "scatter" :mode "lines" :name "A: breadth-first"
:x ts :y (map :fraction (r/reach-curve times-a ts))
:line {:width 2 :color (colors 0) :shape "hv"}}
{:type "scatter" :mode "lines" :name "B: guided by the target"
:x ts :y (map :fraction (r/reach-curve times-b ts))
:line {:width 2 :color (colors 2) :shape "hv"}}]
:layout {:title {:text "Fraction of 30 targets in t-Reachable (seed 7)"}
:xaxis {:title {:text "timer t (ticks = candidates examined)"}}
:yaxis {:title {:text "fraction of targets reached"} :range [0 1.05]}
:legend {:orientation "h" :y -0.25}
:margin {:t 50 :r 20}}})Observation 3.13 (seed 7, 30 targets). Host A reaches all 7,758 behaviours eventually, the last at tick 11,561. Host B’s search is complete on a finite universe (the tests check this for the 3-node universe), so it has the same ω-Reachable. Their t-Reachable sets differ widely. A needs a median of 2,817 ticks and at most 10,802. B needs a median of 133 and at most 751. B is faster on 22 targets and never slower. On the other 8 both find the target in the first layer.
- at most 10,802
- reaches all 7,758 behaviours, the last at tick 11,561
- at most 751
- faster on 22 of 30 targets, never slower
So efficiency is not decided in N-Reachable, which is fixed by the step relation and identical for A and B. It lies in the search strategy: how each host moves through the same sets. B also computes a distance per candidate, and counting elementary operations would shrink its lead by a roughly constant factor. A comparison of speed is fair only when both hosts are timed by the same clock.
12.4 Summary
- The five sets are defined on states, from the host’s step relation (one input write, one own step), and mapped to memes by behaviour. A step relation on memes would overcount.
- “ω-Reachable is independent of Existing” means persistence: no step loses anything from reach. Strong connectivity gives it (Proposition 3.6), and the toy generators have it.
- The reachable sets do not separate open from closed. Saturation follows the size of the behaviour space, and superlinear growth needs combining steps (Proposition 3.9), which closed grammars have.
- Speed is measured with a timer, on states, not memes. With the same reachable sets, a search guided by the evidence reaches its targets about twenty times faster at the median. Efficiency lies in the search strategy.
12.5 Open problems
- Irreversible steps. When is ω-Reachable persistent if forgetting or entrenchment make steps irreversible? Proposition 3.6 covers only the reversible case.
- Active. It plays no role in this step relation, although the seeds of a host’s search plausibly come from it.
- Hyperdimensional versions. The planned open-versus-closed composition experiment (E6) and concept-space search experiment (E7) must count by behaviour, and may not separate open from closed.
- Which search strategy a person uses, and whether it separates a person from an enumerator (post I.2), is not formalised.
12.6 References
- De la Guardia, C. (2025a). The five nested sets of the mind. Making Minds and Making Progress (Substack), 28 May 2025. https://carlosd.substack.com/p/sets (verified: definitions quoted from the page)
- Deutsch, D. & Marletto, C. (2015). Constructor theory of information. Proc. R. Soc. A 471, 20140540. (not re-checked)
- Deutsch, D. & Marletto, C. (2025). Constructor theory of time. arXiv:2505.08692 (v3, June 2026). §5–6. (verified: null constructor and timer attributes checked in the full text)
source: book2/notebooks/meme_constructor/posts/post_03_five_sets_and_time.clj