2 A Constructor Theory of Computing and Design: the programme
(ns meme-constructor.computing.post-i0-programme
(:require [scicloj.kindly.v4.kind :as kind]
[meme-constructor.figures :as fig]))Post I.0 of Part I. Status: September 2026.
Part I asks what computing, persons and design are, in terms abstract enough to cover computers, brains, language models and evolution alike. Its answer in brief: no condition on what a system can reach separates a person from a program enumerator; design needs variation that does not read the task and selection by the task, not competition; and the growth of knowledge needs fallibilism, criticism that makes nothing final, tied to an anchor outside the process.
Part I is the general half of the book. Part II, “Memes as Abstract Constructors”, applies its definitions to ideas in brains, and Part III, “A Constructor Theory of Adaptation”, to living things.
2.1 The question
Constructor theory (Deutsch 2013) states physics as which tasks are possible and which are impossible. A task takes a substrate from input attributes to output attributes. A constructor performs a task and keeps the ability to do it again. An abstract constructor is information that acts as a constructor, such as the genetic information in a recipe rather than the DNA molecule. Formally it is the class of all programs, or brain states, that perform the same tasks. Post 1 restates these terms with section references.
Part I asks what computing is in these terms, what a person is, and what a design is and which processes can make one. Its machine is Push3 (Spector, Klein & Keijzer 2005), a stack language in which programs are data, in posts I.1 to I.4. The experiments of posts I.5 and I.6 run on the bit-string model of post 4, because there the quantities they need can be computed exactly.
2.2 The answer
Programs and persons. A computing system (C1) keeps its own steps apart from the steps the outside world causes. A Push program is then an abstract constructor, and on finite tests its class can be computed. Two conditions a person meets can be stated exactly: no input forces an output, non-programmability (C2), and every behaviour is reachable by the system’s own steps, self-reachability (C3). They separate a person from an idle laptop with a compiler. One might think they define a person. They do not: a laptop running a program enumerator meets them too, and no condition on reachable sets can separate the two (Proposition I.2.14). What survives is persistence: no state the system reaches closes off the alternatives.
- separate a person from an idle laptop with a compiler
- a laptop running a program enumerator meets them too
- no condition on reachable sets separates the two
- no reachable state closes off the alternatives
- necessary, not sufficient
Synthesis. Synthesis (C4) is the task whose product is a program. Over an acceptable language only properties witnessed by finitely many input-output pairs can be confirmed (Rice–Shapiro): one can test a program, never certify it. A decoder that reads a meme off a brain is a verifier of the brain’s own programs, so a receptive host has none.
Design. A design is a constructor most of whose one-step variants perform its task much worse, and it is graded (Definition I.5.0, with the knowledge, alternatives and fine-tuning conditions (D1–D3)). It mentions no process. The adaptive synthesis task (C5) is a process with two conditions: variation that does not read the task, unspecific variation (A1′), and selection by the task (A3). Competition (A2) is a property some such processes have, not a condition. If the variation does not read the task, the design reaches the product only through the eliminator’s decisions, at about one bit per decision, the information bound (S1′). The design conjecture, stated once as Conjecture I.5.12, says that adaptationism is the best theory of design: whatever reliably produces a design without containing it implements the two conditions.
Fallibilism. When the criterion of criticism is itself varied, reflexivity (C8), nothing is ever fixed as final. That is fallibilism (C10), a property of the process, not of the accuracy of any copy. Keeping is as blind as reaching (Proposition I.6.5), so what separates a process that creates knowledge is what its keeping depends on: an external anchor (Conjecture I.6.6). Conjecture I.6.13 is Part I’s positive thesis: creativity is persistence plus anchored criticism. It describes a process, not a class of machines.
2.3 What the experiments show
Five experiments: the Chaitin reproduction (X1), the point-versus-algorithmic experiment (X2), the population-competition experiment (X3), the information-bound experiment (X4) and the reflexive-criterion experiment (X5).
The cumulative-selection proposition (S2) is the known fitness-level method (Wegener 2002). What Part I adds is the constructor-theoretic statement that joins Popper’s and Chaitin’s views of evolution, and mainly the information bound (S1′), the reflexivity proposition (S4) and fallibilism (C10). That evolution and the growth of knowledge are one process is old (Popper 1972, Campbell 1974, Dennett 1995, Deutsch 2011). That evolution should be measured algorithmically is Chaitin’s (2012b).
2.4 Where Part I sits
| Who | What they provide | What Part I adds |
|---|---|---|
| Chaitin (2009, 2012a, 2012b) | organisms as programs, algorithmic mutations, three regimes of search | populations, a criterion that can vary, and a designer that pays for its oracle |
| Deutsch (2011, 2013), Marletto (2015), Deutsch & Marletto (2015) | possible and impossible tasks, abstract constructors, knowledge, “we cannot be programmed” | formal versions of non-programmability and self-reachability, and the proof that they do not define persons |
| Popper (1972), Campbell (1974), Bartley (1962), Dennett (1995) | one process for evolution and knowledge, blind variation, pancritical rationalism | “blind” made precise as “does not read the task”, and the criterion carried in the medium |
| Solomonoff (1964), Levin (1973), Li & Vitányi (2019) | the universal prior, universal search, the invariance theorem | used for algorithmic variation (C6) in post I.4 and for efficiency in post I.2 |
| Kimura (1961), Worden (1995) | selection as a supply of information, per site | a bound for one run and any variator |
Part I owns the general definitions. Part II and Part III take them as given and link to the post that proves them.
2.5 The posts
- Post I.1: Computing systems as constructors. A system’s own steps kept apart from its inputs, and a Push program as an abstract constructor.
- Post I.2: Two conditions for persons. Non-programmability and self-reachability, persistence, and why no such condition separates a person from an enumerator.
- Post I.3: Synthesis, and why one has to run things. One can test a program, never certify it, and a decoder is a verifier.
- Post I.4: Metabiology. Chaitin’s model on Push3: algorithmic variation helps only together with a criterion that rewards the steps.
- Post I.5: The adaptive synthesis task. Design without a process, the two conditions of an adaptive process, the information bound, and the design conjecture.
- Post I.6: From a fixed criterion to Popper. A criterion that is itself varied, the anchor, and fallibilism.
An optional post I.7 on selection as erasure (C9), with the reversible-world experiment (X6), is planned and not written. Nothing in posts I.1 to I.6 depends on it.
Reading order. The order of dependence is Part I, then Part II, then Part III. Read Part I first, or start with Part II and read posts I.1 to I.3 before or next to post 1, and post I.5 before post 7.
2.6 Open problems
- Keeping a design. Finding a design needs no competition. Does keeping one under continuing variation need it, or only selection that keeps reading the task? In post I.6 the same question is the price of fallibilism. It is the central open question of the book.
- Person versus enumerator: the problem of creativity. No condition on reachable or kept sets separates them (Propositions I.2.14 and I.6.5). Conjecture I.6.13 describes a process. Whether anything beyond the anchor separates a person from an enumerator that runs an anchored reflexive process is open, and so is human versus mouse (Conjecture I.2.15).
- A test of Conjecture I.6.13 with a task that moves, comparing a ratchet, an unanchored and an anchored reflexive process.
- The design conjecture as a proof. “Reliably produces” and “contains” are not defined.
- Populations. The information bound (S1′), the cumulative-selection proposition (S2) and the reflexivity proposition (S4) are stated for one lineage.
2.7 References
Only works cited in this post. Entries marked “verified in post I.x” were checked online when that post was written. Their exact passages are given there.
- Bartley, W. W. (1962). The Retreat to Commitment. Knopf. (verified in post I.6)
- Campbell, D. T. (1974). Evolutionary epistemology. In P. A. Schilpp (ed.), The Philosophy of Karl Popper, Open Court, 413–463. (verified: bibliographic data)
- Chaitin, G. J. (2009). Evolution of mutating software. Bulletin of the EATCS 97, 157–164. (verified in post I.4)
- Chaitin, G. J. (2012a). Proving Darwin: Making Biology Mathematical. Pantheon. (verified in post I.4: bibliographic data only)
- Chaitin, G. J. (2012b). Life as evolving software. In H. Zenil (ed.), A Computable Universe, World Scientific, ch. 15. (verified in post I.4: Theorems 1–3 and Open Problem 6)
- Dennett, D. C. (1995). Darwin’s Dangerous Idea: Evolution and the Meanings of Life. Simon & Schuster. (verified: bibliographic data and the reading of natural selection as a substrate-neutral algorithm)
- Deutsch, D. (2011). The Beginning of Infinity. Allen Lane. (not re-checked)
- Deutsch, D. (2013). Constructor theory. Synthese 190(18), 4331–4359. (verified in post I.1)
- Deutsch, D. & Marletto, C. (2015). Constructor theory of information. Proc. R. Soc. A 471: 20140540. (verified in post I.1)
- Kimura, M. (1961). Natural selection as the process of accumulating genetic information in adaptive evolution. Genetical Research 2(1), 127–140. (verified in post I.5)
- Levin, L. A. (1973). Universal sequential search problems. Problems of Information Transmission 9(3), 265–266. (verified in post I.2)
- Li, M. & Vitányi, P. (2019). An Introduction to Kolmogorov Complexity and Its Applications, 4th ed. Springer. (verified in post I.4)
- Marletto, C. (2015). Constructor theory of life. J. R. Soc. Interface 12(104): 20141226. (not re-checked)
- Popper, K. R. (1972). Objective Knowledge: An Evolutionary Approach. Oxford University Press, ch. 7, “Evolution and the tree of knowledge”. (verified: chapter title)
- Solomonoff, R. J. (1964). A formal theory of inductive inference, parts I and II. Information and Control 7, 1–22 and 224–254. (verified in post I.4)
- Spector, L., Klein, J. & Keijzer, M. (2005). The Push3 execution stack and the evolution of control. Proc. GECCO 2005, 1689–1696. (verified in post I.1)
- Wegener, I. (2002). Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. In Evolutionary Optimization, Kluwer, 349–369. (verified in post I.5: bibliographic data)
- Worden, R. P. (1995). A speed limit for evolution. Journal of Theoretical Biology 176(1), 137–152. (verified in post I.5)
source: book2/notebooks/meme_constructor/computing/post_i0_programme.clj