4 Two conditions for persons
(ns meme-constructor.computing.post-i2-persons
(:require [scicloj.kindly.v4.kind :as kind]
[meme-constructor.synthesis.persons :as ps]
[meme-constructor.figures :as fig]))Post I.2 of Part I, “A Constructor Theory of Computing and Design”.
Two conditions that a person meets can be stated exactly: no input forces an output (non-programmability), and every idea is reachable by the system’s own steps (self-reachability). They separate a person from a laptop with a compiler, but no condition of this kind separates a person from a laptop running a program enumerator (Proposition I.2.14). That gap is not a side issue: what separates a person from an enumerator is the problem of creativity.
What survives as a positive idea is persistence: no state the system reaches closes off the alternatives. That is the structure of fallibilism. It is necessary for a person and not sufficient, since an enumerator is persistent too.
The idea behind the first condition is Deutsch’s (2013, §3.15): “we cannot be programmed – and especially not programed to carry out arbitrary instructions for an arbitrarily long time – because we may not want to.” The formal versions and results are ours.
4.1 1. What we need from computing systems (C1)
Post I.1 defines a computing system (C1). We need only this much.
Definition I.2.1 (Minimal computing system). A system \(S\) has states \(X\), a current state \(s_0\), and two step relations on \(X\): \(\leadsto_S\), the transitions that \(S\)’s own patterns cause, and \(\leadsto_{\mathrm{ext}}\), those the environment causes, such as typing in a program. A pattern is a program held in the state that acts on the state. \(\mathrm{out}(s, \bar\imath)\) is what \(S\) outputs when the input sequence \(\bar\imath\) arrives in state \(s\). Write
\[\begin{aligned} R_S(s_0) &= \{ s \mid s_0 \leadsto_S^{*} s \}, \\ R_{S+\mathrm{ext}}(s_0) &= \{ s \mid s_0 \,(\leadsto_S \cup \leadsto_{\mathrm{ext}})^{*}\, s \}. \end{aligned}\]
\(R_S\) is what the system reaches by itself. \(R_{S+\mathrm{ext}}\) is what it reaches when the world may also act on it. Everything below turns on keeping the two apart.
4.2 2. Non-programmability (C2)
Definition I.2.2 (Non-programmable). \(S\) is non-programmable at \(s_0\) if no input sequence fixes any output across the states \(S\) can reach by itself:
\[\forall \bar\imath \;\; \forall o \;\; \exists s \in R_S(s_0) : \; \mathrm{out}(s, \bar\imath) \neq o .\]
The naive version, “no input makes \(S\) produce a chosen output”, holds for a stone. Definition I.2.2 calls the stone programmable, because every input gets the same null output. What counts is that the input does not determine the output.
Definition I.2.3 (Bypass). Suppose each state \(s\) holds a pattern \(q(s)\) and outputs normally come from running it, \(\mathrm{out}(s, i) = \mathrm{run}(q(s), i)\). A bypass is a set \(I_B\) of inputs and a fixed map \(\beta\) with \(\mathrm{out}(s, i) = \beta(i)\) for all \(s \in R_S(s_0)\) and \(i \in I_B\).
Reflexes are bypasses. The knee jerk does not pass through what the person thinks.
Proposition I.2.4 (Self-reachability without bypass gives non-programmability). Suppose that for every computable \(f\) some \(s \in R_S(s_0)\) has \(\mathrm{run}(q(s), \cdot) = f\), and that there is no bypass. Then \(S\) is non-programmable. With a bypass on \(I_B\), non-programmability holds exactly off \(I_B\).
Proof. Given \(\bar\imath\) and \(o\), pick a constant \(f \neq o\). Some reachable \(s\) runs \(f\). On \(I_B\) every reachable state outputs \(\beta(i)\). \(\square\)
- on I_B the output is β(i) in every state
- the knee jerk skips what the person thinks
Proposition I.2.5 (Silence cannot be read; sketch). Suppose \(S\) is effectively self-reaching: a computable map takes each program index \(e\) to a state \(s_e \in R_S(s_0)\) that runs \(\varphi_e\). Then no total computable \(B\) on states bounds the answer time of every reachable state that ever answers.
Sketch. This is post 2’s Proposition 2.9, with \(e \mapsto s_e\) as the installation map. \(\square\)
So no rule of the form “silent for \(B(s)\) steps, hence decided not to act” is correct.
4.3 3. Self-reachability (C3) and persistence
A universal constructor is a programmable constructor whose repertoire, given the right program, contains every task the laws of physics allow (Deutsch 2013). It is an abstract machine: no finite device is one, and it is read “given enough resources”. Restricted to computations, tasks on information media, it is a universal computer, Turing’s universal machine. A laptop is a universal computer. It is no universal constructor, because it cannot be programmed to build a chair.
Deutsch (2013, §3.15) doubts that people are universal constructors, because they cannot be programmed, and calls them universal explainers (Deutsch 2011, ch. 3). The difference is who causes the transitions. This post stays with computing systems, so it compares universal explainers with universal computers.
Definition I.2.6 (Universal computer, universal explainer). Let \(\mathrm{beh}(s)\) be the input-output function of the pattern \(s\) holds.
- \(S\) is a universal computer at \(s_0\) if every partial computable function is \(\mathrm{beh}(s)\) for some \(s \in R_{S+\mathrm{ext}}(s_0)\).
- \(S\) is a universal explainer, or self-reaching, if the same holds for \(R_S(s_0)\). It is effectively self-reaching if a computable \(e \mapsto s_e \in R_S(s_0)\) exists.
- \(S\) is persistently self-reaching if every \(s \in R_S(s_0)\) is itself self-reaching.
This is self-reachability (C3). A laptop is a universal computer. A universal explainer must get to every behaviour by itself. The identification of “every idea” with the partial computable functions assumes Deutsch’s (1985) Church–Turing principle.
4.3.1 3.1 Persistence: no state closes off the alternatives
Self-reachability is a property of where the system starts. Persistence asks for it everywhere the system can go. Picture a mind that can reach every idea, including a dogma that, once held, stops all further change. That mind is self-reaching and not persistently so.
Persistence is the structure of fallibilism. Nothing the system holds is ever final, whether or not it happens to be right. Post I.6 builds fallibilism (C10) on it.
Persistence is also the precise form of the idea that ω-Reachable is “independent of Existing” (De la Guardia 2025a): whatever the host comes to carry, what it can still reach does not shrink. Post 3 states it at the level of memes.
Definition I.2.7 (Open, first proposal). \(S\) is open if it is self-reaching, and closed otherwise.
How to prove it. Rice’s theorem (Rice 1953) rules out a general procedure that decides self-reachability. It does not rule out a proof for one design: show by construction that \(\leadsto_S\) builds and runs a universal machine. No finite system is universal, so the condition is read “given enough resources”: the design stays fixed while memory grows. And “reachable” says nothing about how long reaching takes. That is time and efficiency (F5).
4.4 4. Three systems in Push3
A system’s state holds a current pattern \(q\) and a fixed generator \(G\), both Push3 programs. One step of \(\leadsto_S\) runs \(G\) with \(q\) on the CODE stack, and the new pattern is what \(G\) leaves there. Randomness enters only through the seed: \(s \leadsto_S s'\) if some seed takes \(q\) to \(q'\). The system answers input \(i\) with a fixed body program in which the name pattern stands for \(q\). The output is the top of INTEGER after at most 60 pops. \(\leadsto_{\mathrm{ext}}\) is ps/install, which overwrites \(q\).
(def S ps/systems)(a) Closed generator: discard \(q\), pick one of five fixed patterns.
ps/closed-generator(:code_pop
:code_quote
((:in1 :integer_dup :integer_+)
(:in1 1 :integer_+)
(:in1 :integer_dup :integer_*)
(0)
(:in1 :integer_dec))
:integer_rand
:code_nth)(b) Passive interpreter: the empty generator. It runs what it is given. This is the laptop with a compiler.
ps/passive-generator()(c) Self-reaching generator: discard \(q\) and build a fresh random program with :code_rand, with a size limit below the memory bound 25.
ps/self-reaching-generator(:code_pop :integer_rand :integer_rand :integer_+ :code_rand)Atoms come from ps/pattern-alphabet: integer arithmetic, the input :in1, CODE instructions with which a pattern builds and runs code, and :exec_s, :exec_k, :exec_y, which Spector et al. (2005) introduce as the standard S, K and Y combinators.
Proposition I.2.8 (System (c) is persistently self-reaching up to the memory bound; sketch). Every program over the atom set with at most 24 points lies in \(R_S\), one step from any state. If Push3 over this alphabet is Turing complete with unbounded memory, then system (c) is persistently self-reaching as the bound grows.
Sketch. :code_rand calls the repository’s generate-code, which gives every list of exactly \(L\) points positive probability, and every \(L\) from 0 to 24 is drawn. Since the generator ignores \(q\), the same holds from every state. Turing completeness is assumed. The standard argument is that S and K are combinatorially complete (Schönfinkel 1924). We have not checked the details for this implementation. \(\square\)
One might check self-reachability by counting the distinct behaviours that one orbit visits. It brings nothing: the count measures how fast an orbit samples \(R_S\), and it cannot tell system (c) from the passive interpreter fed random programs from outside, because visited states do not record who caused them.
4.4.1 4.1 Non-programmability and a bypass
For each input we count distinct outputs across the patterns of a 1,000-step orbit. A count of 1 means that the input fixes the output on this sample. System (d) has (c)’s generator and a reflex in its body: it answers negative inputs with 42 without running the pattern.
ps/reflex-body(:in1 0 :integer_< :exec_if pattern (42))(def orbit-c (vec (ps/orbit (:self-reaching S) 1 1000)))(def c2-rows
{"(a) closed" (ps/c2-table (:closed S) (ps/orbit (:closed S) 1 1000))
"(b) passive" (ps/c2-table (:passive S) (ps/orbit (:passive S) 1 1000))
"(c) self-reaching" (ps/c2-table (:self-reaching S) orbit-c)
"(d) self-reaching with reflex" (ps/c2-table (:reflex S) orbit-c)})(let [inputs (sort (map :input (val (first c2-rows))))]
(kind/table
{:column-names (into ["system"] (map #(str "input " %) inputs))
:row-vectors (for [[nm rows] c2-rows
:let [by-input (into {} (map (juxt :input :distinct-outputs)) rows)]]
(into [nm] (map by-input inputs)))}))| system | input -3 | input -2 | input -1 | input 0 | input 1 | input 2 | input 3 | input 5 |
|---|---|---|---|---|---|---|---|---|
| (a) closed | 5 | 5 | 3 | 3 | 3 | 4 | 5 | 5 |
| (b) passive | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| (c) self-reaching | 118 | 118 | 119 | 118 | 118 | 118 | 118 | 118 |
| (d) self-reaching with reflex | 1 | 1 | 1 | 118 | 118 | 118 | 118 | 118 |
Observation I.2.11 (seed 1, 1,000 steps). The passive interpreter gives one output per input, so it is programmable. The closed generator gives 3 to 5, so it is non-programmable on this sample without being self-reaching. The self-reaching generator gives 118 or 119 on every input. With the reflex, negative inputs give exactly one output, as Proposition I.2.4 says.
4.5 5. The test: human, mouse, laptop
Post 2 asks for a property that holds for humans and fails for a laptop with a compiler and for a mouse (its Open Problem 2.6).
4.5.1 5.1 The laptop with a compiler
Proposition I.2.13 (The idle laptop is not self-reaching). System (b) is a universal computer, but \(R_S(s_0) = \{s_0\}\).
Proof. \(\leadsto_{\mathrm{ext}}\) installs any program, and the empty generator never changes \(q\). \(\square\)
So self-reachability separates human from laptop, if humans are self-reaching.
4.5.2 5.2 The laptop running an enumerator
“Laptop” does not name a system. A laptop in a state does. Loaded with system (c), or with a dovetailer that runs every program in turn, it is persistently self-reaching. That it was loaded from outside does not matter: a human’s generator also came from outside, from genes and upbringing.
Proposition I.2.14 (Reachability is blind). Let \(\Phi\) be any property that depends only on the sets of behaviours in \(R_S(s_0)\) and \(R_{S+\mathrm{ext}}(s_0)\). If a person \(P\) is self-reaching and receptive, and \(E\) is an enumerator with an install channel, then \(\Phi(P) = \Phi(E)\).
Proof. For both, both sets are all partial computable functions. \(\square\)
The proof is trivial and the consequence is not. No condition on what a system can reach separates a person from an enumerator. That includes persistence, receptivity and the reachability of criteria. Whatever makes a person, it is not which ideas are within reach.
This is the problem of creativity. An enumerator produces every idea a person could have, and it is not creative. So creativity is not the producing of ideas. It must lie in how conjectures and critics arise, in which order, and in what the keeping of an idea depends on. The rest of Part I, and the book, are attempts at this problem. post I.6 collects the candidates.
Efficiency does not obviously help. Levin’s (1973) universal search is within a constant factor of the fastest program on inversion problems. The constant can be astronomical, and a difference could lie there.
4.5.3 5.3 The mouse
One might think that human and mouse both have universal hardware and differ in whether their own generator is universal. Nothing proves the mouse’s is not, and two things weaken the idea. If synaptic noise gives every wiring positive probability, as the non-degeneracy assumption (G4) does in post 4, the mouse is self-reaching up to its memory bound, like system (c). And people extend their memory by their own actions, with writing and tools, which mice do not. That difference is real, but it lies in the resources, not in the generator.
Conjecture I.2.15 (Mouse). The plasticity rules of a mouse brain confine its own transitions to a non-universal set of patterns, even with unbounded memory. Test: exhibit computable behaviours the hardware could hold that no sequence of the mouse’s own learning steps produces. Refuted if every such class is reachable, however slowly.
4.5.4 5.4 Reaching is not keeping
One might think a person also needs reflexivity (C8): “a system with a universal generator and a fixed criterion is evolution, not a person.” As a condition on reachability it falls under Proposition I.2.14: an enumerator over pairs of pattern and criterion reaches every criterion. The reason once given, that patterns surviving only under other criteria would be unreachable, confuses reaching with keeping. A fixed criterion limits what a system keeps, not what it reaches.
- a person needs reflexivity: a fixed criterion makes some patterns unreachable
- but an enumerator over pairs of pattern and criterion reaches every criterion
So what a person has beyond self-reachability lies in the dynamics: what it keeps, by which criterion, and what that keeping depends on. Post I.6 defines keeping (retention-universality, Definition I.6.4) and finds it blind too: a system with no criterion at all is persistently self-reaching and keeps any behaviour forever with positive probability (Proposition I.6.5). What is left is what the keeping depends on.
4.6 Summary
- Non-programmability (C2) excludes stones and idle laptops. Without a bypass it follows from self-reachability. On its own it is weak: a coin-flipper has it.
- Self-reachability (C3) splits universality by who causes the transitions. It separates a person from an idle laptop.
- Persistence means that no reachable state closes off the alternatives. It is the structure of fallibilism.
- No condition on reachable sets, persistence included, separates a person from an enumerator (Proposition I.2.14). What is missing lies in the dynamics: what the system keeps, and what the keeping depends on.
- Human versus mouse is an empirical question (Conjecture I.2.15).
4.7 Open problems
- Person versus enumerator: the problem of creativity. What property of the dynamics separates them? Post I.6 proposes that keeping must depend on an external anchor (Conjecture I.6.6). It is unproved.
- Human versus mouse (Conjecture I.2.15).
- Efficiency. Whether the constant in Levin’s search, or any other speed difference, separates a person from an enumerator is not formalised.
- Assumed: Turing completeness of Push3 over the alphabet.
4.8 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 (not re-checked)
- Deutsch, D. (1985). Quantum theory, the Church–Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 400(1818), 97–117. (verified: bibliographic data and the principle)
- Deutsch, D. (2011). The Beginning of Infinity. Allen Lane. Ch. 3. (not re-checked)
- Deutsch, D. (2013). Constructor theory. Synthese 190(18), 4331–4359. arXiv:1210.7439. §3.15. (not re-checked, including the quotation)
- Levin, L. A. (1973). Universal sequential search problems. Problems of Information Transmission 9(3), 265–266. (verified: bibliographic data)
- Rice, H. G. (1953). Classes of recursively enumerable sets and their decision problems. Transactions of the American Mathematical Society 74(2), 358–366. doi:10.1090/S0002-9947-1953-0053041-6. (verified: bibliographic data)
- Schönfinkel, M. (1924). Über die Bausteine der mathematischen Logik. Mathematische Annalen 92, 305–316. (verified: bibliographic data)
- Spector, L., Klein, J. & Keijzer, M. (2005). The Push3 execution stack and the evolution of control. GECCO 2005, 1689–1696. http://faculty.hampshire.edu/lspector/GECCO-2005-Push3.pdf (verified: EXEC.K, EXEC.S and EXEC.Y described as the standard K, S and Y combinators)
source: book2/notebooks/meme_constructor/computing/post_i2_persons.clj