3 Computing systems as constructors
(ns meme-constructor.computing.post-i1-computing-systems
(:require [scicloj.kindly.v4.kind :as kind]
[meme-constructor.synthesis.system :as sys]
[meme-constructor.synthesis.timer :as tm]
[meme-constructor.figures :as fig]))Post I.1 of Part I, “A Constructor Theory of Computing and Design”.
A computing system is a substrate whose programs act on the system itself, and the one distinction that matters is who causes a step: the system’s own programs, or the outside world. With that distinction in place, a Push3 program is an abstract constructor, and the class of programs that do the same thing can be computed on a finite test set.
This post fixes the machine and the vocabulary for Part I. Part II uses the same definitions for brains.
3.1 1. Computing systems (C1)
We take substrate, attribute, task, constructor and information variable from constructor theory, as restated in post 1 (Definitions 1.1–1.5). An information variable is a set of attributes that can be permuted and copied (Deutsch & Marletto 2015, §3). The one extra notion we need is Deutsch’s programmable constructor: a constructor whose behaviour is set by a program it holds, as a ribosome’s product is set by the RNA (Deutsch 2013, §2.1).
Definition I.1.1 (Computing system). A computing system \(S\) is a substrate with state space \(X\) in which some variables are information variables. Among them are an input medium and an output medium \(M\). The rest is the system’s interior.
Definition I.1.2 (Pattern). A pattern \(p\) of \(S\) is an abstract constructor that is instantiated in the information variables of \(S\) and performs tasks \(x \to x'\) on \(S\) itself.
A pattern is both constructor and substrate. It lies in the states it transforms and can transform itself. This is the programmable constructor turned inward: the program is part of the machine’s state.
Definition I.1.3 (Step relations). The internal step relation is
\[\leadsto_S \;=\; \{\, (x, x') \in X \times X \mid \text{some pattern in } x \text{ takes } x \text{ to } x' \text{ in one step} \,\}.\]
The external step relation \(\leadsto_{\mathrm{ext}}\) contains the transitions caused from outside. Two kinds matter. Writes to the input medium form \(\leadsto_{\mathrm{in}} \subseteq \leadsto_{\mathrm{ext}}\). Writes to the interior, which install or change patterns, are programming.
- a pattern in the state takes x to x′
- outputs are internal steps
- input writes ⇝in: to the input medium
- programming: writes that install or change patterns
Definition I.1.4 (Output). An output is a step of \(\leadsto_S\) that changes the output medium \(M\). For a brain, \(M\) is the muscles. For a computer, \(M\) is a display, a file or an actuator.
The split between \(\leadsto_S\) and \(\leadsto_{\mathrm{ext}}\) is the point of the definition. A laptop can be brought to run any program, but only by programming from outside. Whether a system reaches every program by its own steps is a different property, self-reachability (C3), and it is the subject of post I.2.
The step relation \(\leadsto_H\) of a host in post 3 (Definition 3.1) takes \(s\) to \(s'\) “for some input”. In the present terms it is one input write followed by one internal step:
\[s \leadsto_H s' \iff \exists\, u:\ s \leadsto_{\mathrm{in}} u \leadsto_S s', \quad\text{so}\quad \leadsto_H \;=\; \leadsto_S \circ \leadsto_{\mathrm{in}} .\]
3.1.1 1.1 Push3 as a computing system
Push3 (Spector, Klein & Keijzer 2005) is a stack language built for program synthesis, with one stack per type: INTEGER, BOOLEAN, CODE, EXEC and more. EXEC holds what is still to be executed. The interpreter pops its top and lets it act: a literal is pushed, an instruction transforms the state, a list is unpacked onto EXEC. We use the implementation in benjamin-schwerdtner-clj-push3 unchanged.
In the terms of Definition I.1.1:
Here is the program (:in1 :in1 :integer_+ 1 :integer_+) running after the input \(n = 3\) was written from outside.
(def two-n-plus-one '(:in1 :in1 :integer_+ 1 :integer_+))(defn stack-table [states]
(kind/table
(map-indexed (fn [i s]
{:step i
:exec (pr-str (get-in s [:stacks :push/exec]))
:integer (pr-str (get-in s [:stacks :push/integer]))})
states)))(stack-table
(sys/trajectory (-> (sys/empty-state) (sys/with-input 3) (sys/load-program two-n-plus-one))
50))| step | exec | integer |
|---|---|---|
| 0 | [(:in1 :in1 :integer_+ 1 :integer_+)] | [] |
| 1 | [:integer_+ 1 :integer_+ :in1 :in1] | [] |
| 2 | [:integer_+ 1 :integer_+ :in1 3] | [] |
| 3 | [:integer_+ 1 :integer_+ :in1] | [3] |
| 4 | [:integer_+ 1 :integer_+ 3] | [3] |
| 5 | [:integer_+ 1 :integer_+] | [3 3] |
| 6 | [:integer_+ 1] | [6] |
| 7 | [:integer_+] | [6 1] |
| 8 | [] | [7] |
The top of each vector is its right end. Eight steps leave 7 on INTEGER and an empty EXEC. The program is consumed as it runs, and an empty EXEC means the system has halted.
3.1.2 1.2 A constructor theory of software
Software is easy to place in constructor theory, because the theory was built around the universal computer (Deutsch 1985). It is a tower of programmable constructors, and only the bottom of the tower is hardware. Here is the tower on which every Push program of Part I runs.
At the bottom is a circuit: gates, each doing an elementary task on a few bits, wired so that the laws of physics carry out the computation. In a classical computer these are logic gates, in a quantum computer a quantum circuit. To write a computation into a circuit is to build the constructor.
A processor is a circuit that is a programmable constructor. Its machine language is what von Neumann called the complete code, the machine’s “primary” language. An interpreter is a program in one machine’s code that makes the machine perform the tasks of another machine, whose programs are written in a more convenient language, a short code or “secondary” language. That is Turing’s universal machine simulating a given one (von Neumann 1966, editor’s introduction; von Neumann 1958). The simulated machine is a virtual machine: a programmable constructor that is itself an abstract constructor, existing only as a program on another machine.
Read this way, software is an abstract constructor running on a programmable constructor. It is substrate-independent for a plain reason: each layer needs only that the layer below performs its tasks, not how. The same Push program is the same abstract constructor on any tower that runs Push3, although, as Proposition I.1.12 below shows, not at the same speed.
Constructor theory adds one distinction that the usual picture blurs. A programmable constructor told to mimic another constructor \(C\) may either simulate \(C\) step by step, as an interpreter does, or first build an instance of \(C\) and then pass the inputs to it, so that from then on the task costs about what \(C\) itself would cost (Deutsch 2013, §3.7). The first is interpretation, the second is compilation carried to the end, and that is why the theory can define the repertoire of a programmable constructor up to a constant overhead.
- run C's program step by step
- every step of C costs many steps of the host
- the interpreter stays in the loop
- first build an instance of C
- then pass the inputs to it
- from then on the task costs about what C costs
Von Neumann suggested that the nervous system, too, has a primary language, very different from any language we know (von Neumann 1958). The book reads a meme the same way: an abstract constructor running on a brain whose complete code nobody writes down (post 1).
3.2 2. The Push program as an abstract constructor
Definition I.1.5 (Task and constructor on Push). The substrate is the Push state. An attribute is a set of Push states, for example “the top of INTEGER is 7”. A task on a test set \(D\) of inputs is
\[\sigma = \{\, \mathrm{in}(x) \to \mathrm{out}(y) \mid x \in D \,\},\]
where \(\mathrm{in}(x)\) is the attribute “input \(x\) is written” and \(\mathrm{out}(y)\) is “halted, with \(y\) in the output medium”. Halting is required because a constructor must signal that it is done (Deutsch 2013, §3.13). A constructor for \(\sigma\) is the interpreter together with a stored program.
The word stored matters. The copy on EXEC is used up, and a constructor must keep its ability to perform the task again (Deutsch 2013). In Push the program can be kept as a named binding. When the interpreter meets the name, it pushes a copy of the bound program onto EXEC.
- holds the program
- unchanged after every call
- pushed at each call
- used up as it runs
(def gauss-tri '(:in1 :in1 :integer_inc :integer_* 2 :integer_div))(let [s0 (sys/define (sys/empty-state) 'tri gauss-tri)
s1 (sys/call-stored s0 'tri 4)
s2 (sys/call-stored s1 'tri 10)]
{:after-first-call (sys/view s1)
:after-second-call (sys/view s2)}){:after-first-call
{:stacks #:push{:integer [10N]},
:input {:in1 4},
:bindings {tri (:in1 :in1 :integer_inc :integer_* 2 :integer_div)}},
:after-second-call
{:stacks #:push{:integer [55N]},
:input {:in1 10},
:bindings {tri (:in1 :in1 :integer_inc :integer_* 2 :integer_div)}}}The program computes \(n(n+1)/2\). It ran on 4 and on 10 (the N marks a Clojure BigInt), and the binding is unchanged. This is Marletto’s (2015) split between recipe and vehicle in miniature: the genome stays, each execution is spent. It is only an analogy, since nothing protects the binding: a program can redefine its own name.
Definition I.1.6 (Abstract constructor on Push). Fix a task universe: a test set \(D\) and a step budget \(B\). The repertoire \(T(p)\) of a program \(p\) is the set of tasks \(x \to y\), with \(x \in D\), that \(p\) performs, halting within \(B\) steps. For a task \(\sigma\) the abstract constructor is
\[K_\sigma = \{\, p \mid \sigma \subseteq T(p) \,\}.\]
If \(p\) halts on all of \(D\), its class is \(K_\sigma\) with \(\sigma = T(p)\): all programs with the same input-output map on \(D\).
This is the meme as equivalence class (F2) of post 1, with programs in place of brain states. There, \(b\) carries \(m\) iff \(T_m \subseteq T(b)\) (Definition 1.7). Here \(p \in K_\sigma\) iff \(\sigma \subseteq T(p)\). What is new is that for finite \(D\) and \(B\) the classes can be computed.
Seven programs, grouped by their input-output map on \(D = \{0, 1, 2, 3\}\) and then on \(D = \{0, \ldots, 7\}\):
(def examples
{:a two-n-plus-one
:b '(:in1 2 :integer_* :integer_inc)
:c '(1 :in1 :in1 :integer_+ :integer_+)
:d '(0 :in1 :exec_do*count (:integer_pop 2 :integer_+) :integer_inc)
:e '(:in1 2 :integer_* :integer_inc 7 :integer_min)
:f '(:in1 :in1 :integer_*)
:g '(:in1 :integer_dup :integer_*)})(defn group-names [test-set]
(into (sorted-map)
(map (fn [[io ps]] [(pr-str io) (mapv (fn [p] (some (fn [[k v]] (when (= v p) k)) examples)) ps)]))
(sys/classes (vals examples) test-set))){:on-0-to-3 (group-names (range 4))
:on-0-to-7 (group-names (range 8))}{:on-0-to-3 {"[0 1 4 9]" [:f :g], "[1 3 5 7]" [:a :b :c :d :e]},
:on-0-to-7
{"[0 1 4 9 16 25 36 49]" [:f :g],
"[1 3 5 7 7 7 7 7]" [:e],
"[1 3 5 7 9 11 13 15]" [:a :b :c :d]}}Observation I.1.7 (no seed; deterministic). On \(\{0,1,2,3\}\) the seven programs fall into two classes: a to e compute \(2n+1\) (d with a loop), f and g compute \(n^2\). On \(\{0, \ldots, 7\}\) program e leaves its class, because it caps its result at 7. A finite test set approximates the classes from above. A larger one can split classes, never merge them.
How far off is the approximation? We enumerate all flat programs of length 1 to 5 over eight symbols and group them on two test sets.
(def alphabet [:in1 1 2 :integer_+ :integer_* :integer_inc :integer_dup :integer_swap])(def enumerated (sys/enumerate-programs alphabet 5))(def classes-4 (sys/classes enumerated (range 4)))(def classes-10 (sys/classes enumerated (range 10))){:programs (count enumerated)
:classes-on-0-to-3 (count classes-4)
:classes-on-0-to-9 (count classes-10)
:size-of-2n+1-class (count (classes-4 [1 3 5 7]))}{:programs 37448,
:classes-on-0-to-3 41,
:classes-on-0-to-9 41,
:size-of-2n+1-class 163}Observation I.1.8 (no seed; exhaustive). The 37,448 programs fall into 41 classes on \(\{0,1,2,3\}\), and into the same 41 on \(\{0, \ldots, 9\}\). No class splits. The class of \(2n+1\) has 163 members. The largest classes are the constant functions.
That so few inputs suffice is no accident.
Proposition I.1.9 (Finite tests decide a polynomial fragment). Let every program in a set \(P\) compute, on a range where no value is clamped, either nothing or an integer polynomial in \(n\) of degree at most \(d\). Then any \(d+1\) distinct test inputs in that range separate every two classes of \(P\).
Proof. Two distinct polynomials of degree at most \(d\) agree on at most \(d\) points, and “nothing” differs from every polynomial on every input. \(\square\)
Our alphabet meets the hypothesis: +, *, inc, dup and swap build every stack item from \(n\) and constants by addition and multiplication. The degrees of the 41 classes, read off by finite differences:
(defn degree
"Degree of the polynomial through the values ys at 0, 1, 2, ...
(-1 for the zero polynomial)."
[ys]
(loop [ys ys, d 0]
(if (every? zero? ys) (dec d) (recur (map - (rest ys) ys) (inc d)))))(->> (keys classes-10)
(remove #(some #{:none} %))
(map degree)
frequencies
(into (sorted-map))){0 12, 1 14, 2 12, 3 1, 4 1}The largest degree is 4, so five inputs are guaranteed to suffice, and four happened to. Program e above is outside the fragment: :integer_min breaks polynomiality, and with it the guarantee. With loops, conditionals and CODE manipulation the language is universal, no finite test set fixes the class of every program, and membership \(p \in K_\sigma\) over all inputs is undecidable (Rice 1953). Synthesis (C4) in post I.3 draws the consequence: one can test a candidate, never certify it.
- +, *, inc, dup, swap: every class is a polynomial
- degree ≤ 4, so five inputs suffice (Prop. I.1.9)
- loops, conditionals, CODE manipulation: universal
- no finite test fixes every class (Rice 1953)
3.3 3. The timer as a Push program
Post 3 imports the timers of Deutsch & Marletto (2025) to define time-bounded tasks and t-Reachable (time and efficiency (F5)). A timer of duration \(t\) is an isolated system that shows “running” until it shows “done”, and “done” stays. It needs an executable form, and here it is.
Definition I.1.10 (Counter timer). The timer program is (0 :exec_y :integer_inc): push 0, then repeat :integer_inc forever. It runs in a Push state of its own, and a fixed scheduler alternates one step of the task system with one step of the timer. For a duration \(t\) the timer shows running while the counter is below \(t\) and done once it reaches \(t\).
No instruction of the task can reach the timer’s state, so the timer is isolated by construction, as Deutsch & Marletto’s eq. (8) requires. One program gives timers of every duration. Under a fixed schedule the timer is a rescaled step budget and adds no numbers of its own. What it settles is where speed belongs.
Three programs compute \(n(n+1)/2\) for \(n \ge 1\): one loops over a count, one sums a range, one uses Gauss’s formula.
(def loop-tri '(0 :in1 :exec_do*count (:integer_inc :integer_+)))(def range-tri '(0 1 :in1 :exec_do*range :integer_+))(def tri-task (into {} (map (fn [n] [n (quot (* n (inc n)) 2)])) (range 1 41)))(def tri-programs {"loop over count" loop-tri
"loop over range" range-tri
"Gauss formula" gauss-tri})(def t-fixed 30)(kind/table
(for [[k p] tri-programs]
{:program k
:performs-task? (sys/performs? p tri-task 1000)
:min-duration (tm/min-duration p tri-task)
:largest-n-within-t-30 (last (take-while #(tm/t-constructor? p {% (tri-task %)} t-fixed)
(range 1 41)))}))| program | performs-task? | min-duration | largest-n-within-t-30 |
|---|---|---|---|
| loop over count | true | 95 | 12 |
| loop over range | true | 68 | 17 |
| Gauss formula | true | 3 | 40 |
Observation I.1.11 (no seed; deterministic). All three programs are in the same abstract constructor for \(\sigma = \{ n \to n(n+1)/2 \mid 1 \le n \le 40 \}\). The durations they need differ by a factor of about 30. With a timer of duration 30, the count loop is a t-constructor up to \(n = 12\), the range loop up to \(n = 17\), and the formula for all 40.
Proposition I.1.12 (Speed is not a property of the abstract constructor). Being a t-constructor for \(\sigma\) is not invariant under membership of \(K_\sigma\).
Proof. Observation I.1.11 gives two members of \(K_\sigma\), one a t-constructor for \(\sigma\) at \(t = 30\) and one not. \(\square\)
The proposition is trivial, but it fixes where efficiency sits. The abstract constructor says what is done. How fast belongs to the instance. So t-Reachable must be defined over states and projected to classes, as post 3 does.
A timer that counts down does not make time run backwards. Reversal would need an injective step function, and Push3 has none, since almost every instruction erases information (Landauer 1961); a reversible fragment would have to keep what it erases, as in Bennett’s (1973) construction.
3.4 Summary
- A computing system is a substrate whose patterns act on the system itself. Its own steps \(\leadsto_S\) are kept apart from inputs and programming, \(\leadsto_{\mathrm{ext}}\). Post 3’s host step relation is \(\leadsto_S \circ \leadsto_{\mathrm{in}}\).
- Software is a stack of programmable constructors on a physical circuit: complete code, interpreters for short codes, virtual machines. Software is an abstract constructor running on a programmable constructor.
- A Push program is an abstract constructor in the sense of post 1. The constructor is interpreter plus stored program: the copy on EXEC is spent, the stored program stays.
- On finite test sets the classes can be computed. 37,448 short programs fall into 41 classes, and in this polynomial fragment five test inputs decide membership exactly. Beyond it no finite test does.
- Members of one abstract constructor differ about thirtyfold in the time they need. Speed belongs to instances, not to classes.
3.5 Open problems
- The scheduler is outside the world. The relative rate of task and timer is set by hand. Two steps per tick would change every duration without any program changing, so durations are comparable only under one schedule.
- The output medium is a convention. Push has no separate output substrate. We read the top of INTEGER. The output registers or the PRINT stack would be closer to Definition I.1.4.
3.6 References
- Bennett, C. H. (1973). Logical reversibility of computation. IBM Journal of Research and Development 17(6), 525–532. doi:10.1147/rd.176.0525. (verified: bibliographic data and abstract)
- Deutsch, D. (2013). Constructor theory. Synthese 190(18), 4331–4359. arXiv:1210.7439. §2.1 (programmable constructor), §3.7 (repertoires of programmable constructors), §3.13 (halting). (verified: the passages read in the arXiv text)
- Deutsch, D. & Marletto, C. (2015). Constructor theory of information. Proc. R. Soc. A 471: 20140540. arXiv:1405.5563. §3 (computation and information variables). (verified: definitions read in the arXiv text)
- Deutsch, D. & Marletto, C. (2025). Constructor theory of time. arXiv:2505.08692 (v3, June 2026). §5–6, eq. (8). (verified: timer attributes and the isolation condition read in the full text)
- Deutsch, D. (1985). Quantum theory, the Church–Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 400(1818), 97–117. (verified in post I.2: bibliographic data and the principle)
- Landauer, R. (1961). Irreversibility and heat generation in the computing process. IBM Journal of Research and Development 5(3), 183–191. doi:10.1147/rd.53.0183. (verified: bibliographic data)
- Marletto, C. (2015). Constructor theory of life. J. R. Soc. Interface 12(104): 20141226. arXiv:1407.0681. (not re-checked)
- von Neumann, J. (1958). The Computer and the Brain. Yale University Press, pp. 70–73 (short code and complete code; primary and secondary language). (cited via Burks’s introduction to von Neumann 1966; not checked separately)
- von Neumann, J. (1966). Theory of Self-Reproducing Automata. Edited and completed by A. W. Burks. University of Illinois Press. Editor’s introduction. (verified: the passage on short code, complete code and simulation, in the archive.org full text)
- Rice, H. G. (1953). Classes of recursively enumerable sets and their decision problems. Transactions of the American Mathematical Society 74(2), 358–366. (not re-checked)
- Spector, L., Klein, J. & Keijzer, M. (2005). The Push3 execution stack and the evolution of control. Proc. GECCO 2005, 1689–1696. (verified: bibliographic data)
source: book2/notebooks/meme_constructor/computing/post_i1_computing_systems.clj