11 Open and closed, and why thoughts cannot be read off
(ns meme-constructor.posts.post-02-open-closed-decoding
(:require [scicloj.kindly.v4.kind :as kind]
[meme-constructor.figures :as fig]))Post 2 of Part II, “Memes as Abstract Constructors”.
A decoder that reads a meme off a brain state is a verifier of the brain’s own programs (post I.3, Proposition I.3.5). So no host whose reachable programs form an acceptable language has a full decoder. The limit of decoding runs along the questions, not between open and closed hosts. “Does the host answer \(o\) to \(i\)?” is decodable when the host’s answers are guaranteed to arrive. “Does it never do X?” can be undecidable even for a host that is not universal.
The general way to find out what a host thinks is to ask it. Running its program on the question is the one procedure that is right whenever it answers, and the host is a physical implementation of that procedure.
The post takes three results of Part I as given. Post I.1 separates a system’s own steps from those its environment causes. Post I.2 uses that split to define self-reachability (C3), and with it open and closed. Post I.3 shows that a decoder is a verifier in the sense of synthesis (C4). We use the notation of post 1: \(T(b)\) is the repertoire of a brain state \(b\), \(T_m\) that of a meme \(m\), and \(b\) carries \(m\) iff \(T_m \subseteq T(b)\) (Definitions 1.6 and 1.7).
11.1 1. Two examples
A chimpanzee’s termite-fishing routine is an ape meme: its repertoire is fixed by a string over a fixed alphabet of steps, copied digitally. It could be stored as a small program built from a fixed grammar: if at a mound, strip a twig, then twice probe and lick. However obscurely the brain codes it, someone who knows the code can parse the state and read off what the animal will do in each of its few situations, without running anything.
Now a laptop with a compiler, loaded with some program. Does it ever answer 1 to the question 0? Deciding that for every program the laptop could hold is the halting problem. Knowing the code does not help. The program is the code.
What separates the two cases is not how the state is coded, and not whether the host is creative. It is the question asked and the language of programs the host can hold. The rest of the post makes that precise.
One might call a host closed if everything it can reach “is generated by a fixed repertoire (E, G)” of elements and combination rules. That separates nothing, because every host, creative ones included, is a fixed program running on hardware with fixed laws (Deutsch 2012).
11.2 2. A host model
Definition 2.1 (Host model). A host model is a tuple
\[H = (S, \mathrm{exec}, R_H, R_H^{\mathrm{own}}).\]
\(S\) is a decidable set of finite codes, the host’s possible states. \(\mathrm{exec} : S \times \mathbb{N} \rightharpoonup \mathbb{N}\) is a partial computable function with a step count: \(\mathrm{exec}(s, i)\) is what the host in state \(s\) answers to question \(i\), undefined if it never answers. The reachable sets come from post I.2 (Definition I.2.1):
\[\begin{aligned} R_H &= R_{S+\mathrm{ext}}(s_0), \\ R_H^{\mathrm{own}} &= R_S(s_0) \subseteq R_H . \end{aligned}\]
\(R_H\) is what the host reaches with outside help: inputs, evidence and programming. \(R_H^{\mathrm{own}}\) is what it reaches by its own steps. For an idle laptop with a compiler the two differ completely: \(R_H\) holds every program anyone can type in, \(R_H^{\mathrm{own}}\) the current state alone (post I.2, Proposition I.2.13).
Definition 2.2 (Repertoire, functional identity). Take the task universe \(\mathcal{T} = \mathbb{N} \times \mathbb{N}\), a task being a question-answer pair \((i \mapsto o)\). The repertoire of a state is the graph of its behaviour,
\[T(s) = \{\, (i \mapsto o) \mid \mathrm{exec}(s, i) = o \,\}.\]
This is post 1’s Definition 1.6 for one particular \(\mathcal{T}\). Meme identity is extensional: what counts is the behaviour, not the code.
Definition 2.3 (Question, decoder). A question is a set \(P\) of repertoires, for example “carries \(m\)”, \(P = \{T \mid T_m \subseteq T\}\). A decoder for \(P\) on a set \(R \subseteq S\) is a total computable \(D : S \to \{0, 1\}\) with
\[D(s) = 1 \iff T(s) \in P \qquad \text{for all } s \in R .\]
A decoder on \(H\) is one on \(R_H\). The finite-task questions \(P_{i,o} = \{T \mid (i \mapsto o) \in T\}\) ask “answers \(o\) to \(i\)”. A full decoder decodes every finite-task question.
The state \(s\) already is a complete description of its memes: it is the program. Reading off means turning that description into answers about the repertoire in finite time, correctly for every reachable state.
Definition 2.4 (Universal, effectively receptive). Let \(\varphi_e\) be a standard numbering of the partial computable functions. \(H\) is universal if every \(\varphi_e\) is the behaviour of some \(s \in R_H\). It is effectively receptive if moreover a total computable installation map \(\iota : \mathbb{N} \to R_H\) has \(\mathrm{exec}(\iota(e), \cdot) = \varphi_e\) for all \(e\).
In words: given any program text, a fixed mechanical procedure puts the host into a reachable state that runs exactly that program. A laptop with a compiler has this. A person who can follow written instructions has an approximate version (Section 4.2). The same notions on \(R_H^{\mathrm{own}}\) are self-reachability (C3) and effective self-reachability (post I.2, Definition I.2.6).
11.3 3. Open and closed hosts (F6)
Definition 2.5 (Open, closed). A host is open if it is self-reaching and closed otherwise: post I.2’s Definition I.2.7, read on \(R_H^{\mathrm{own}}\).
Read on \(R_H\) instead, the idle laptop would count as open. Read on the host’s own steps, it is closed. Universal hardware is not enough either. “The human brain does have Turing completeness … But this isn’t enough for intelligence, as it’s ubiquitous” (De la Guardia, quoted in Chipkin 2025). The mouse’s cortex is built much like ours. The table places universality at three sets and adds what we would want “open” to mean. Level B′ is self-reaching (C3).
Definition 2.5 is level B′. It separates a person from the idle laptop, and from the mouse if the mouse’s own learning steps are confined to a non-universal set of patterns (Conjecture I.2.15). It does not reach level C. A laptop running a program enumerator is self-reaching (post I.2, Proposition I.2.8), and no property that depends only on the reachable sets separates a self-reaching, receptive person from an enumerator with an install channel (Proposition I.2.14). So open versus closed is not the line between persons and the rest.
Open Problem 2.6 (Open and closed hosts (F6)). Find a property \(\mathrm{Open}(H)\) of host models such that (a) it implies effective receptivity, at least approximately, (b) it holds for humans and fails for an idle laptop with a compiler, for a laptop running a program enumerator and for a mouse, and (c) it is stated without the word “explicable”, which has no formal definition here.
By Proposition I.2.14 the answer must be a property of the dynamics, not of the reachable sets. Three candidates:
- Receptivity from underdetermined evidence. A person rebuilds a meme from behaviour and speech that underdetermine it (post 1, Proposition 1.11). A laptop needs the program text. This cannot simply be identification in the limit from positive examples, since Gold (1967) showed that no learner, people included, identifies every language of a class that holds all finite languages and one infinite one. The evidence has to include explanations and criticism.
- What the host keeps, and what the keeping depends on. A trained ML system has one fixed criterion, “not itself open to improvement from within the system” (De la Guardia 2020). As reachability this falls under Proposition I.2.14 as well. Post I.6 proposes that keeping must depend on an external anchor (Conjecture I.6.6).
- Efficiency. A person and an enumerator reach the same programs, but not equally fast (post 3).
The decoder question does not need the answer. It already lives at level B, and on the host’s own steps at level B′.
The same holds for non-programmability (C2, Definition I.2.2): no input fixes an output across the states the host reaches by itself. Deutsch (2013, §3.15) says people “cannot be programmed … because we may not want to”. Without a bypass, such as a reflex, it follows from self-reachability (Proposition I.2.4). A coin-flipper has it too, so it adds no test of its own.
11.4 4. The decoder dichotomy (F7): decoding is verification
11.4.1 4.1 A decoder is a verifier
A question is a set of repertoires, so “does \(s\) carry a meme with property \(P\)” is a property of the function \(s\) computes, not of its text. Rice (1953) proved that no non-trivial property of this kind is decidable. Post I.3 states this as a theorem about synthesis: over an acceptable language, one into which every standard numbering translates by a total computable map, verifying a candidate against a specification is undecidable (Proposition I.3.3). Read the reachable states of a host, with \(\mathrm{exec}\), as a language whose programs are states. Then a decoder for \(P\) is exactly a verifier for \(P\) in that language (Proposition I.3.5). Decoding a brain and verifying a candidate program are one problem. Effective receptivity makes the language acceptable, with the installation map as translation.
Proposition 2.7 (No decoder for effectively receptive hosts). Let \(H\) be effectively receptive and \(P\) a question that some partial computable function has and some other lacks. Then \(P\) has no decoder on \(H\). In particular no finite-task question \(P_{i,o}\) has one, and for a meme with finite non-empty \(T_m\), “carries \(m\)” has none. If \(H\) is effectively self-reaching, the same holds for decoders on \(R_H^{\mathrm{own}}\).
Proof. This is post I.3’s Corollary I.3.6. Unfolded: if \(D\) decodes \(P\) on \(H\), then \(D \circ \iota\) is total computable and \(D(\iota(e)) = 1 \iff \varphi_e \in P\), so the index set of \(P\) is decidable, contrary to Rice’s theorem. \(P_{i,o}\) is non-trivial, since the constant function \(o\) has it and the empty function lacks it; the same holds for “carries \(m\)”. For the last sentence, replace \(\iota\) by the map \(e \mapsto s_e \in R_H^{\mathrm{own}}\) of effective self-reachability. \(\square\)
For \(P_{0,1}\) the proof needs no Rice. From a program \(p\) build \(p'\): run \(p\) on input 0, and if it halts, output 1. A decoder for \(P_{0,1}\) would decide whether \(p\) halts, which Turing (1936) showed impossible.
The last sentence of the proposition matters for people. It needs no programming from outside, only that the host’s own steps reach a computable family of programs.
11.4.2 4.2 What the proof needs
Whether Proposition 2.7 says anything about brains depends on hypotheses that are easy to leave unstated.
- Digital states and computable dynamics. This holds if brain states have finite digital descriptions at the relevant grain and Deutsch’s (1985) Church–Turing principle holds: “every finitely realizible physical system can be perfectly simulated by a universal model computing machine operating by finite means”. If brains did something uncomputable, Rice would not apply in either direction. Coding tasks as pairs of integers is then a change of notation.
- An acceptable language, not merely a universal one. Friedberg
- constructed a computable numbering \(\psi\) of all partial computable functions in which every function occurs exactly once. A host whose states are Friedberg indices is universal, yet “is my behaviour \(\psi_0\)?” has the decidable index set \(\{0\}\). So a universal host can have a decoder for a non-trivial question. (This observation is ours. It uses only the existence of the numbering.) What a decoder needs to be impossible is not that every program is present, but that programs can be translated in: receptivity, or on the own part effective self-reachability.
- Exact installation. The translation must hit \(\varphi_e\) exactly. For the function of culture memes, rebuilt from reasons by an open host, no copy is guaranteed or confirmed exact (post 1, Proposition 1.11). Ape memes are different: parsed into a digital alphabet, they are copied arbitrarily accurately, so for them the hypothesis holds. The proof for \(P_{0,1}\) needs less: the host only has to reach exactly the programs of one schema, “run \(p\), then say 1”, and on the own part nobody has to install them. For a person that is still an idealisation. For a laptop it is literal. With a translation that errs on an undecidable set of programs the proof breaks, and we have no replacement.
- Every state, and exactly. A decoder must be right on every reachable state. Rice says nothing about one brain in one state, and nothing against a decoder that is right with probability 0.999 over some distribution of states. For any fixed distribution, running each state for longer and longer becomes arbitrarily accurate, because each halting state halts at some finite time. Rice forbids a decoder that is always right, not one that is usually right. But usually-right decoding of this kind is decoding by running.
So Proposition 2.7 proves: a digital, computable host whose reachable programs form an acceptable language has no full decoder. Applying it to people idealises hypotheses 1 and 3.
11.4.3 4.3 What running can do
Proposition 2.8 (Running is a semi-decoder). For every host model, each \(P_{i,o}\) is semi-decidable on \(S\): run \(\mathrm{exec}(s, i)\) and say yes if it returns \(o\). This never gives a wrong yes. For an effectively receptive host it cannot be completed to a decoder (Proposition 2.7). \(\square\)
Rice–Shapiro sharpens this (post I.3, Proposition I.3.4). Over an acceptable language a property can be confirmed by any procedure at all only if finitely many input-output pairs witness it. “Answers 0 to every question” is not even semi-decidable.
Proposition 2.9 (No computable step budget). If \(H\) is effectively receptive, no total computable \(B : S \to \mathbb{N}\) has the property that every \(s \in R_H\) that answers question 0 does so within \(B(s)\) steps. The same holds on \(R_H^{\mathrm{own}}\) if \(H\) is effectively self-reaching.
Proof. Run \(s\) for \(B(s)\) steps on question 0. If it has not answered, it never will. That decides “answers question 0” on \(R_H\), contrary to Proposition 2.7. \(\square\)
On the own part this says that silence cannot be read: no rule “silent for \(B(s)\) steps, hence decided not to act” is correct (post I.2, Proposition I.2.5).
Corollary 2.10 (“The person is her own decoder”). For an effectively receptive host, the general procedure that is right whenever it answers is to run the host’s program on the question. Putting a question to the host is running its program on it. A scan followed by a complete emulation runs the same procedure on another substrate, at the extra cost of measurement. One would still have to ask the copy.
- the same procedure on another substrate
- extra cost: the measurement
- one would still have to ask the copy
Running needs no creativity: a fixed universal interpreter semi-decodes every meme of such a host. Nor does anything here show that asking is the fastest way.
Conjecture 2.11 (Asking is efficient). For human hosts, no procedure that starts from a brain measurement answers finite-task questions faster on average than asking the person, once the cost of measurement is counted. Test: a neural decoder that predicts a person’s answers to new questions faster and more accurately than the person gives them, without having been trained on that person’s answers, refutes it. It is a claim about efficiency (post 3), not computability, and Proposition 2.7 gives it no support.
11.4.4 4.4 The closed side, and where the limit runs
Proposition 2.12 (Parser decoder). Suppose (i) every \(s \in R_H\) is \(\mathrm{enc}(d)\) for a derivation \(d\) of a context-free grammar \(G\), with \(\mathrm{enc}\) injective, \(S\) decidable and \(\mathrm{enc}^{-1}\) computable, and (ii) the repertoire is a total computable function \(d \mapsto T(d)\) into finite tables. Then every decidable question on finite tables, in particular every finite-task question and meme equality, has a decoder.
Proof. \(D(s) = P(T(\mathrm{parse}(\mathrm{enc}^{-1}(s))))\). Parsing against a context-free grammar is decidable, for example with the CYK algorithm, and every step is total. \(\square\)
This is the chimpanzee of Section 1, and in post I.3’s language it is decidable verification in a closed language. The operative hypothesis is not “non-universal”. It is that the semantics is total and finite. Non-universality alone is not enough:
Proposition 2.13 (Non-universal hosts can lack decoders; sketch). Let \(R_H\) consist of programs with bounded loops only, whose loop counts are fixed on entry, and let installation be computable. Every such program halts on every input, so \(H\) is not universal, and every finite-task question has a decoder: run the program. But the question \(Z\), “answers 0 to every question”, has no decoder.
Sketch. “Machine \(e\) halts on input 0 within \(n\) steps” is computable by a bounded-loop program in \((e, n)\). So for each \(e\) there is a bounded-loop \(z_e\), computable from \(e\), with \(z_e(n) = 1\) if \(e\) halts within \(n\) steps and 0 otherwise. Then \(z_e \in Z\) iff \(e\) never halts. \(\square\)
So the line between decodable and undecodable runs through the questions. An ape whose memes are finite behaviour tables over its behaviour alphabet is fully decodable. An ape whose programs have loops of unbounded but finite length is decodable for single situations, not for “never attacks”.
One might hope for the dichotomy “a non-creative decoder exists iff the host is closed”. It does not hold in either direction, as the figure below shows. The idle laptop has no full decoder on \(R_H\) because it is effectively receptive. The same goes for LLMs: a full decoder for one would show that it is not effectively receptive, but the absence of a decoder shows nothing about creativity. A weaker line between memes and closed behaviour programs survives.
- idle laptop: closed, not creative, no full decoder
- bounded-loop host: closed, no decoder for a global question
- ape meme or other closed behaviour program: a string over a fixed alphabet, in the reach of a host with a parser decoder (Prop. 2.12)
- culture meme (meme in the narrow sense): the function, rebuilt from reasons, in no such host's reach
Running small hosts illustrates all of this and proves none of it: an experimenter who runs random counter machines is in the decoder’s position, and the cases still running when the budget ends stay unanswered.
11.5 Summary
- A decoder is a verifier of the host’s own language (post I.3). So a digital, computable host whose reachable programs form an acceptable language has no full decoder, from outside or on its own steps (Proposition 2.7). Universality alone is not enough (Friedberg).
- The limit of decoding runs along the questions. A parser decodes a host whose memes are finite behaviour tables. A total, non-universal host can still lack a decoder for “never does X”.
- The general decoder is to ask: running the program is the semi-decoder (Corollary 2.10). That asking is also the most efficient route is Conjecture 2.11.
- Open means self-reaching on the host’s own steps (post I.2). It separates a person from an idle laptop, not from an enumerator, so the open-closed line is not the person line.
- “Decodable iff closed” does not hold in either direction.
11.6 Open problems
- Open Problem 2.6: a property of the dynamics that separates a person from a laptop, an enumerator and a mouse.
- Conjecture 2.11: asking is the most efficient decoder.
- The Friedberg case: which questions are decodable for a host that is universal but not acceptable.
- Inexact installation: a version of Proposition 2.7 for hosts whose own steps reach programs only approximately.
11.7 References
- Chipkin, L. (2025). The three pillars of an artificial mind (Fellow spotlight on Carlos De la Guardia). Conjecture Institute. https://conjectureinstitute.org/articles/fellow-spotlight/carlos-de-la-guardia (verified: the Turing-completeness quote is on the page)
- De la Guardia, C. (2020). A few questions on AGI. Making Minds and Making Progress (Substack). https://carlosd.substack.com/p/6-a-few-questions-on-agi (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)
- Deutsch, D. (2012). Creative blocks. Aeon, October 2012. (not re-checked)
- Deutsch, D. (2013). Constructor theory. Synthese 190(18), 4331–4359. arXiv:1210.7439. §3.15. (not re-checked, including the quotation)
- Friedberg, R. M. (1958). Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication. Journal of Symbolic Logic 23(3), 309–316. (verified)
- Gold, E. M. (1967). Language identification in the limit. Information and Control 10, 447–474. (verified)
- 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 and statement checked online via secondary sources; the AMS full text was not accessible from here)
- Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc. s2-42, 230–265. (verified)
source: book2/notebooks/meme_constructor/posts/post_02_open_closed_decoding.clj