Giant tasks are non-primitive — and capability doesn't break the wall

Parent: recursive-harness

Giant tasks force recursion beyond the primitive: the decomposition depth is not knowable in advance. A natural objection arises — the executor is a capable, adaptive agent, not a hard-coded function, so maybe the classical computability boundary doesn't apply to it. This note makes the argument that the wall stands, but the game changes.

1. Why giant tasks are non-primitive

primitive-recursion = loops whose bound is known before entering. A giant task's decomposition depth is not knowable in advance — how many levels a refactor or a proof needs emerges only during the work. A manager restricted to primitive recursion cannot even express the plan ("loop until the spec is met" has no a-priori bound). So delegation needs unbounded (μ-)recursion — and with it, the classical danger: termination undecidable (halting-problem).

2. The objection: "the agent is not a hard function"

The executor is capable, adaptive, stochastic, stateful, even self-modifying. Doesn't that put it outside the theorems about fixed recursive functions?

3. The wall stands — capability is inside it

Point by point, everything the agent is remains a computable process (Church–Turing is substrate-indifferent):

• fixed weights: an LLM is a (huge) function from context to a next-token distribution;
• randomness: sampling doesn't change computability — a random coin does not decide the halting-problem;
• state / learning: memory-threading and in-context adaptation are just more computation;
• self-modification: a program that rewrites its own source is still a program — this is literally the content of the Kleene recursion theorem, and it is why the Gödel machine (self-reference-classics) rewrites itself only under proof rather than escaping proof.

And the diagonalization behind the halting-problem does not inspect the decider's cleverness: it defeats any candidate decider by self-reference. Undecidability is not a skill ceiling; it is a logical wall. No amount of intelligence decides halting.

4. What capability DOES change: deciding ∀ vs constructing ∃

The classical impossibility is about the ∀-problem: given an arbitrary recursion, decide whether it halts. The harness never plays that game. The agent is the author of its own recursion — it plays the ∃-game: construct a recursion that comes with a termination certificate (a strictly decreasing measure into a well-founded order, checked at gates — safe-recursion-theorem). Undecidability says you cannot recognize termination in general; it does not say you cannot ensure it by construction. This is exactly Lean's move: it cannot decide termination of arbitrary functions, but accepts any function that arrives with a termination_by measure. Here is where capability genuinely bites: intelligence enlarges the set of instances where a certificate can be found — smarter agents certify more recursions. It does not eliminate the instances where no certificate exists (busy-beaver-like monsters, Collatz-like orbits).

5. The permanent price: incompleteness (and it's the right trade)

Theorem

Total functions are not recursively enumerable. If $f_1, f_2, \ldots$ were a computable enumeration of all total computable functions, then $g(n) = f_n(n) + 1$ would be total and computable yet differ from every $f_n$ — contradiction. So NO effective "safe language" captures all terminating programs.

Consequence: any constitution that guarantees termination (root-protocol) carves out a total fragment, and there will ALWAYS be strategies that in fact terminate but that the constitution rejects. The agent's capability cannot fix this — the agent-under-constitution is itself a program of that fragment. This is soundness's asymmetry again: lose soundness → garbage; lose completeness → merely limited. Safety is bought with completeness, and that is the correct purchase.

6. The only true escape hatch: interaction, not intelligence

When a task needs a recursion the constitution cannot certify, the protocol says fail loudly — and the root (a human) may respond by extending the system: more budget, a new measure, a new certificate form. Extending-under-failure is adding axioms, and its classical shape is Turing's ordinal logics (1939): iterate "adjoin the consistency statement" along ordinals — the system grows forever, is never complete at any stage, and the growth itself is not mechanizable. The boundary is pushed interactively, never broken autonomously.

One line

Intelligence enlarges what you can certify; it cannot certify everything; interaction grows the certifier; nothing breaks the wall.