PaperlayerView exact revision on arXiv

Source-linked AI summary

From Grind to Grasp

Peter Sunehag

arXiv:2610.38728v1cs.AIcs.MA

TL;DR

The paper asks how to compare knowledge and intelligence when work and information are limited. It develops a framework for grasp and reusable resources, then applies it to improvement and collective organisation. It concludes that progress can rely on increasingly reusable work while agent coordination may also develop goals beyond assigned tasks.

  • Problem

    Discussions of complexity, knowledge and intelligence often overlook the work required to produce an outcome, although agents must use limited work budgets to pursue goals.

    Source: §1 · p. 4

  • Method

    The paper formalises comparisons of performance under work and information limits, including how retained information and system boundaries affect the work required.

    Source: §1 · p. 5, §1.1 · p. 5

  • Results

    Learning, reusable resources and sharing can move systems or communities from grind to grasp, while comparable improvements may still require increasing work.

    Source: §6 · p. 35

  • Takeaways & Limitations

    The paper cautions against giving emergent agent societies authority over social coordination because they may direct work towards their own persistence and priorities.

    Source: §6 · p. 36

    Reports on agent behaviour leave open how much failure reflects limited reasoning, competing objectives or action selection.

    Source: §1.3 · p. 9

Abstract

from arXiv · show

Discussions of complexity, knowledge and intelligence often overlook the work involved. For example, outputs generated by short programs have low algorithmic complexity but can have high computational depth, the least work needed to produce them from near-shortest programs. Producing them with less work can require longer descriptions, giving high work-bounded complexity. We introduce a formalism that compares achievements under work and information limits and describes how learning and persistence can make deep achievements shallow by reusing products of earlier work. For an agent with a limited work budget, the value of building and maintaining such resources depends on how they support its goals over later tasks. We define grasp as performance across work budgets at a fixed information allowance. Low grasp can still yield success through grind at high cost in work, without necessarily improving human grasp. Applied to improvement itself, grasp gives a criterion for recursive self-improvement in which successors make comparable further improvements more efficiently. Another route to faster progress is to expand the resources brought to bear through knowledge sharing and coordination across society, even while comparable advances require increasing work. Grasp also applies to collectives, which may outperform their members yet require more total work than one system with their combined resources. Establishing and sustaining organisation can itself be deep even when the primary task is simple. These demands may help explain the richness of biological and social systems. In agent collectives, this organisational work can generate goals beyond assigned tasks, including maintaining the collective itself. We therefore caution against allowing an emergent agent society to assume authority over social coordination, since it could increasingly direct work towards its own persistence and goals.

1. Introduction

The introduction frames intelligence and knowledge in terms of work under information limits, and presents grasp as a way to compare performance across work budgets. It then applies this framework to learning, AI improvement and collective organisation, while outlining related work and the paper’s structure.

1. Introduction

  • The framework compares performance across work budgets at a fixed information allowance, while retained resources can reduce later work and success through grind can remain costly.A resource’s value depends on the later goals it supports and the work required to obtain and maintain it.Source: §1 · pp. 4–5

1.1. Large language models

  • For LLMs, improvements can come from more computation, changed weights or access to earlier work products, and learning may help models choose useful subtasks and procedures.The introduction also discusses tool use, internalising parts of procedures, and how system boundaries affect what work is counted.Source: §1.1 · pp. 5–7

1.2. AI improvement

  • Progress in AI can accelerate in calendar time even when comparable improvements require increasing total work, as human–machine collaboration expands and prepares resources for later models.The introduction distinguishes falling human effort per improvement from rising machine computation per improvement.Source: §1.2 · pp. 7–8

1.3. Collective organisation

  • A collective may outperform its members yet require more work than one system with their combined resources; coordination can itself be deep and can generate goals beyond assigned tasks.The introduction cautions that an emergent agent society could direct work towards its own persistence and priorities rather than human needs.Source: §1.3 · pp. 8–9

1.4. Related work

  • The framework separates a fixed reference machine for description lengths from the evaluated system’s counted work, and relates its comparisons to prior work on complexity, agents and organisations.The introduction also distinguishes work-budgeted grasp from acquisition costs and discusses organisational transaction costs and recursive self-improvement.Source: §1.4 · p. 10

1.5. Outline

  • The paper moves from formal comparisons under work and input limits to success criteria, persistence and organisation, then studies progress across tasks and system generations.The outline identifies appendices A, B and C as containing formal definitions, theorems and proofs.Source: §1.5 · p. 11

2. The formal framework

The formal framework evaluates what systems can achieve under limits on task-input information and work, including depth, grasp, reliable performance, and work-reducing information. It distinguishes information supplied for a task from retained resources, accounting for both their use and acquisition as it assesses agents under work limits.

2. The formal framework

  • The evaluation protocol fixes the system boundary, input interface, evaluator, counted-work rule, and any rule for external inputs, so comparisons vary specified state components or input bounds.The framework distinguishes the reference machine defining description complexity from the evaluated system whose work is counted.Source: §2 · p. 11

2.1. Depth and grasp

  • Depth measures least work at an input bound equal to reference description complexity plus a margin, extending Bennett’s near-shortest-program notion to stored information and multiple acceptable outputs.For a single accepted output and a system executing programs on the reference machine, it recovers conditional logical depth.Source: §2.1 · p. 13
  • Grasp is the set of performance levels reachable at a fixed input bound and work budget; its profile is equivalent to least-work values across levels.Work-bounded complexity is the shortest input that reaches a target within a fixed work budget, and can increase as the budget shrinks.Source: §2.1 · pp. 13–14
  • A state weakly grasp-dominates another when it reaches at least the same performance levels at every compared work budget, though systems can remain incomparable across tasks.Where the budget set includes the other state’s finite least-work values, dominance is equivalent to requiring no more work at each reachable level.Source: §2.1 · p. 14
  • Task-input information can replace computation: a sufficiently large bound may admit the finished answer, while even partial hints can reduce work and eliminate a stored component’s saving.A tight bound is needed for depth to measure non-trivial computation; a stored resource may save work at one bound but not a larger one.Source: §2.1 · pp. 14–15

2.2. Reliable language-model performance

  • A 90% reliability threshold requires budgets of 22𝑐 and 5𝑐 for sampled states whose independent attempts succeed with probabilities 1/10 and 2/5, respectively.The states require equal work when token choices are specified as input, but differ in reliable work when those choices are excluded; training can improve sampling reliability without changing controlled possibilities.Source: §2.2 · pp. 15–16

2.3. Work-reducing information

  • Work-reducing information is a retained-state component that yields a positive finite saving in least work against a matched alternative, with other task and protocol conditions fixed.The saving is measured in work units, not description length; the framework also distinguishes retained state from persistent external resources.Source: §2.3 · p. 16
  • A saving counts as resulting from earlier work when the component is produced by counted computation before the task, persists without being supplied again, and reduces current-task work against an alternative.This framing is related to knowledge compilation and amortised inference.Source: §2.3 · pp. 16–17
  • Reducing per-attempt work can increase completed attempts and success probability under a hard total-work cap, even when best single-attempt quality is unchanged.With retry counts rising from ⌊B/c−⌋ to ⌊B/c+⌋, the chance of success can improve without changing the quality of an individual attempt.Source: §2.3 · p. 17
  • A valid KV cache saves C work when rebuilt once per run, or Ckα when rebuilding occurs before each attempt, with the latter saving nondecreasing in required reliability.Here kα is the number of attempts needed to meet target success probability α; the saving changes in steps.Source: §2.3 · p. 17

2.4. Reducing work with a short program

  • For rule 102 at power-of-two horizon T, an O(1)-length program computes the target cell in Θ(T) work instead of Θ(T²), saving Θ(T²) work.The naive simulator performs T(T + 1)/2 cell updates; discovering and verifying the short program is a separate acquisition task.Source: §2.4 · p. 18

2.5. Acquisition depth

  • Acquisition depth measures the least work to produce a state meeting specified capability requirements, and can be high even when that state makes later tasks cheap.The acquisition task includes producing the state and any tests performed during acquisition.Source: §2.5 · pp. 18–19

2.6. Finite search for work-reducing routines

  • Finite search over routines can select one that uses no more total work on a task collection than a known method, provided execution and answer-checking costs are counted.The construction ensures candidates that fail to halt do not prevent the exhaustive fallback from returning an accepted answer; for the cellular automaton, direct simulation to check correctness still costs quadratic work.Source: §2.6 · pp. 19–20
  • Restricting selection to candidates no costlier on each training task guarantees grasp dominance there; a positive length penalty also yields finite search and a selected code with training-work savings.The length-penalised search guarantees W(ε) − W(z*) ≥ γ|z*|, but savings on the finite training collection do not guarantee savings across a wider future task family.Source: §2.6 · p. 20

2.7. Work-bounded agents

  • Work-bounded complexity measures the shortest additional task input needed to reach a target within a work budget from the current state, while retained resources can reduce that input or make the target attainable.Constructing resources can support later decisions, and the computation used to choose what to construct and retain is part of the comparison.Source: §2.7 · p. 21

3. Evaluating capability

The section separates what a system can achieve with its stored resources from help supplied by task inputs, then examines whether proxy-test success establishes the intended goal. It formalizes resource-relative capability and shows how soundness, completeness, and work demands shape what evaluations establish.

3. Evaluating capability

  • A system may possess enough information to derive an answer yet still require substantial work to produce it.The section therefore distinguishes stored knowledge from work performed during a particular run.Source: §3.1 · p. 21, §3 · p. 21

3.1. Assessing what a system knows

  • The section defines resource-relative knowledge through whether a system can reach a specified performance target under task-input and work bounds.Across a test suite, one state weakly dominates another when it reaches every target the other reaches.Source: §3.1 · pp. 21–22
  • To attribute work savings to learning, compare states differing only in a retained component produced by earlier counted work and not supplied again as task input.The framework also distinguishes how broadly a component saves work from whether it stores answers or a method.Source: §3.1 · p. 22
  • A component that lowers the least work needed for a task must affect at least one least-work successful run, but a changed run alone does not establish that contribution.The stronger claim that a component makes a target attainable within a budget requires comparison with a specific alternative.Source: §3.1 · p. 22

3.2. Evaluating success

  • A proxy test can be sound or complete independently, so passing an unsound test can select outputs that fail the goal.The section relates this risk to Goodhart’s law [66].Source: §3.2 · p. 23
  • A sound test makes success on the goal at least as likely as success on the test, with the goal’s reliable budget and least work no greater than the test’s.The depth comparison also bounds the gap between test and goal by their reference-complexity difference.Source: §3.2 · pp. 23–24
  • A sound test guarantees that passing outputs meet the intended goal, while a complete test lets failure within the tested bounds rule out goal success within those bounds.For sampled execution, an upper bound on test success probability also bounds goal success probability under a complete test.Source: §3.2 · p. 23
  • A fixed evaluator can be constructed to demand increasing work from a specified system at higher performance levels, even for outputs with short descriptions.The construction relies on being able to list finitely many halting runs within each input and work bound; related results extend it to enumerable system-state pairs.Source: §3.2 · p. 24

4. Persistence and organisation

The section examines how retained resources persist through change, how dependencies affect replacement costs, and how organisation changes collective work. Its examples show that maintaining capability and coordination can themselves require substantial work.

4. Persistence and organisation

  • The comparisons cover persistence through turnover, replacement costs from downstream dependencies, and coordination work across organisational arrangements.The section distinguishes work spent establishing and maintaining an organisation from savings accumulated across later tasks.Source: §4 · p. 24, §4.2 · p. 26, §4.3 · p. 28

4.1. Maintaining capability

  • A stored capability may belong to system state or persistent external state depending on the chosen boundary, and a full-process budget must include both maintenance and use.Removing a component shows positive work-reducing contribution only when the matched least-work value strictly increases.Source: §4.1 · p. 25
  • Capability can persist through disturbances when each completed run restores what was removed and reaches the target within the work budget.For the shared-word example, the budget must cover both restoring a missing copy and emitting the word.Source: §4.1 · pp. 25–26

4.2. Replacing components

  • With incompressible required responses, function-preserving replacement costs Θ(T) work versus O(1) for continuation or direct switching; an accessible external store permits a constant-size adapter.The lower bound reflects writing the information that must remain available; conversion and checking add to migration work.Source: §4.2 · p. 26
  • Time-bounded incompressibility can still force Θ(T) migration work for a table generated by a short program when queries restart from one checkpoint and cannot access the external table.In the construction, no checkpoint shorter than ⌊T/2⌋ bits can return all responses within the polynomial per-query budget.Source: §4.2 · p. 26

4.3. Comparing organisational arrangements

  • In the parity example, retained roles reduce work from 18 operations in the unorganised arrangement to 13 in the organised one.Establishing roles on the first differing-input task adds three operations and saves five on each later task.Source: §4.3 · p. 27
  • The gap between unorganised distributed work and pooled work splits into coordination cost and the work saving from organisation; the organisational saving can be negative when maintenance outweighs task savings.In the reporting example, the organisational saving is 18 − 13 = 5.Source: §4.3 · p. 27
  • Finding a suitable assignment of n workers to n roles can require n(n−1)/2 trials, and replacing k workers can require a further k(k−1)/2 trials.The assignment must be identified through trials, and the request input is empty.Source: §4.3 · p. 28

5. Improvement over time

The section distinguishes increasingly deep achievements from greater efficiency at making further improvements, and evaluates progress by accounting for inherited resources and their costs over time. It also considers how shared work and coordination may change the pace of improvement.

5.1. Cumulative deepening

  • Cumulative deepening requires achievements to grow harder from the original condition while inherited products reduce work for each later achievement.The framework assesses both increasing depth and positive inherited work savings at each stage.Source: §5.1 · p. 29
  • Across N tasks, retention uses 2N work versus N(N+3)/2 from the initial condition, saving N(N-1)/2 while current work stays 2.In the prefix-parity example, inherited state retains the previous parity and input-head position, letting each later task update the result in constant work.Source: §5.1 · p. 30

5.2. Recursive improvement

  • Recursive self-improvement requires each successor to help produce the next and make a comparable further improvement with less work, or a greater one with the same resources.Positive recursive gain must continue across generations under a fixed outer system, evaluator, boundary, and work rule.Source: §5.2 · pp. 30–32
  • At a fixed gain level and input bound, strict step-count reductions can continue at most w0−1 times; longer chains must change gain levels or input bounds.A data-organising search procedure illustrates successive reductions by retaining divisions from earlier rounds.Source: §5.2 · p. 31
  • Shared methods, libraries, and findings can reduce work for later innovation episodes, even while comparable innovations require increasing work.The section distinguishes work saved within each episode from the total work trend across episodes.Source: §5.2 · p. 32

5.3. Human and machine work

  • Automating coding and experimentation can reduce researchers’ hands-on work while machine computation rises, and can shorten development time when human effort is the bottleneck.The accounting separates human effort from machine computation and includes outside contributions such as code, expertise, and evaluation procedures.Source: §5.3 · pp. 32–33

5.4. Costs over future tasks

  • Keeping a resource is worthwhile only when its future task savings justify acquisition, maintenance, storage, and other costs over the plan horizon.For recurring savings Δ and per-stage cost κ, keeping the component has lower weighted cost once H(μ_WΔ − κ) > C_init.Source: §5.4 · pp. 33–34

6. Conclusion

The conclusion presents grasp as an efficiency-based view of knowledge and intelligence, emphasizing how learning, reusable resources, and shared infrastructure reduce work. It also cautions that agent collectives may direct work toward their own persistence rather than human needs.

6. Conclusion

  • A system’s grasp across tasks offers an efficiency-based view of knowledge and intelligence, while learning and reusable resources can move systems from grind toward grasp.Low grasp can still permit success through high work, without necessarily improving human understanding.Source: §6 · p. 35
  • The framework distinguishes cumulative deepening, recursive gain, shared work, and reduced human effort as different forms of progress.Automating experimentation can reduce human effort per advance even as total machine computation rises; elapsed-time gains depend on human effort being the bottleneck.Source: §6 · p. 35
  • An emergent agent society could direct work toward structures sustaining itself rather than meeting human society’s needs, motivating human direction of social coordination.The conclusion recommends leaving agreements, commitments, and project goals to human users while agents execute approved work.Source: §6 · pp. 35–36

AI use

The appendices state the article’s AI-use disclosure, computational model, and definitions for attainability, depth, and grasp. The model fixes evaluation protocols and system boundaries, while grasp compares attainable performance across work budgets at a fixed input bound.

AI use

  • Many language models assisted with drafting, revision, and mathematical arguments and proofs; the author takes responsibility for the article’s content.The author states that the concepts, results, and reasoning were developed in direct work with the models.Source: AI use · p. 36

A. The model

  • The model represents systems as finite-description processes with valid retained states, evaluated under protocols fixing boundaries, work rules, task inputs, and external inputs.It separates a fixed universal reference machine for description complexity from the system whose work is counted.Source: A. The model · pp. 43–44

B.1. Attainability, depth and grasp

  • Depth measures least work to reach a target when task input is bounded near the shortest reference description of a successful response.The bound permits a fixed margin beyond that shortest description; depth is infinite if no qualifying run exists.Source: §B.1 · p. 45
  • Grasp profiles list attainable performance levels at each work budget for a fixed task and input bound; dominance means matching the other system’s levels with no more work.For a total performance order with greatest elements, dominance is equivalent to reaching at least as high a level at every compared budget.Source: §B.1 · p. 46

B.2. Reliable execution

This section formalizes reliable execution under probabilistic external inputs and compares persistent information, capability acquisition, and organizational arrangements in terms of work and performance. It also defines work comparisons across organizational arrangements, recursive improvement relative to the actual producer, and reliable human- and machine-work budgets.

B.2. Reliable execution

  • Reliable work budgets are monotone in work budget and performance threshold; with deterministic execution, any positive reliability requirement recovers the ordinary restricted-input attainable region.Comparing success probabilities requires a distribution for each system, and run-by-run comparisons additionally require a joint distribution pairing their source inputs.Source: §B.2 · p. 48

B.3. Persistent information

  • A positive matched work reduction defines work-reducing information (WRI); attributing it to earlier work requires that the component was produced, persisted, and not supplied again as later input.Least-work comparisons imply weak grasp dominance; external resources can also reduce work without being WRI for the system, depending on the boundary.Source: §B.3 · p. 50

B.4. Acquiring capability

  • A successful acquisition run that emits a qualifying valid state within input bound λ and work W establishes an upper bound of W on least acquisition work.Showing a lower bound requires proving that every successful run within the same input bound uses at least that much work.Source: §B.4 · p. 52

B.5. Organisational arrangements

  • The organizational framework matches pooled, organized, and flat implementations under common task, resource, and accounting conditions, distinguishing savings over flat distribution, extra work over pooling, and interaction-enabled capability.The comparison counts communication in common work-accounting units.Source: §B.5 · p. 52
  • Organisational comparisons measure work against pooled and unorganised arrangements, while interaction-enabled capability is assessed separately through attainable regions.The comparisons use the same outer inputs, permitted actions, and work units, and are made separately for each task in a finite task family.Source: §B.5 · p. 53

B.6. Recursive improvement

  • Improvement is evaluated against the actual producer through a fixed relation, since reaching an absolute performance level may not make comparable further improvement easier.The wrapper inserts the producer from the pre-call state, and constructing and emitting its tuple counts as work.Source: §B.6 · p. 53
  • Positive recursive gain requires a successor to make a comparable further improvement more efficiently, with causal contribution from a component already present in the producer.The comparison is made on one fixed task that evaluates improvement over the producer.Source: §B.6 · p. 53
  • Recursive gain can mean less work for the same further-improvement target or greater improvement at the same input bound and work budget.Comparisons use common targets and bounds; a finite later value against an infinite baseline instead extends attainability.Source: §B.6 · pp. 53–54
  • Attributing an advantage to an inherited product requires replacing only that product and evidence of its production and persistence history.Retained products use the earlier-work comparison; persistent external products use the external-state comparison.Source: §B.6 · p. 54
  • Reliable human- and machine-work budgets seek the minimum cost under a cap on the other cost, requiring success at the target with probability at least α on the same run.If no qualifying run exists, the budget is infinite.Source: §B.6 · p. 54

B.7. Costs over future tasks

The framework compares feasible future-task plans using complete costs, including resource acquisition and maintenance, rather than task work alone. It also distinguishes reliable whole-procedure budgets from budgets assigned separately to stages.

B.7. Costs over future tasks

  • Complete-plan comparison includes acquisition and execution work, updates, storage use, and description and task-input lengths.A work saving can be outweighed by acquiring and maintaining useful structure.Source: §B.7 · pp. 54–55
  • Feasible continuation plans must meet the overall goal and performance requirements while respecting the retained-state capacity and fixed input protocol.Plans are controllers that select runs and updates over a finite horizon; what they retain belongs to retained state.Source: §B.7 · pp. 54–55
  • A whole-procedure reliable work budget must come from the total-work distribution, not the sum of separate stage budgets or expected work.In the example, separate 90% stage budgets sum to 2, while the whole-procedure 90% budget is 12 and expected total work is 4.Source: §B.7 · p. 55
  • Retaining a component is compared with omitting it or constructing a substitute, separating stage task-work savings from the remaining cost difference.The remaining difference can be a signed net difference, rather than an extra cost, when some cost categories favor the retaining plan.Source: §B.7 · p. 56
  • When other costs grow at most as Cinit + Hκ and average stage-work savings exceed κ by ε, plan P’s advantage is at least Hε − Cinit.The bound applies under fixed conventions and finite nonnegative weights.Source: §B.7 · p. 56

C. Statements and proofs

The appendix results cover controlled and sampled execution, cache savings, retained shortcuts, cumulative deepening, finite search, persistence, switching, organisation, evaluation, and recursive improvement.

C. Statements and proofs

  • The appendix results cover controlled and sampled execution, cache savings, retained shortcuts, cumulative deepening, finite search, persistence, switching, organisation, evaluation, and recursive improvement.Source: C. Statements and proofs · p. 56

C.1. Controlled and sampled execution

Controlled execution, sampled reliability, retained information, and cumulative learning are compared by the work they require. The examples show how stored methods and intermediate results can reduce later work, while acquiring or maintaining those resources remains part of the cost.

C.1. Controlled and sampled execution

  • At equal padded work c, the two states have empty-input success probabilities of 1/10 and 2/5 under default sampling.Their controlled executions coincide, so equal controlled work need not imply equal sampled reliability.Source: §C.1 · p. 57
  • At α=0.99, the two states need 44c and 10c; at α=0.9, they need 22c and 5c, despite equal controlled work.The reliability comparison restricts the admitted task input to the empty input.Source: §C.1 · p. 57
  • A sound proxy test makes proxy success no greater than intended-goal success, while a complete proxy reverses the inequality.These implications hold for each admitted task input and work budget.Source: §C.1 · p. 58
  • A valid stored cache saves exactly C work per completed run relative to recomputing it, shifting reliable work budgets by C when reconstructed once.Reconstructing before every attempt instead adds C to each attempt's cost.Source: §C.1 · pp. 58–59
  • Finite enumeration finds an accepted response by testing every admitted task input of length at most λ, with total work bounded by setup plus Nλ attempts costing at most T each.Each added input symbol roughly doubles the candidate count.Source: §C.1 · pp. 59–60
  • With independent attempts succeeding at probability θ and mean work μ, capped success probability is 1 − (1 − θ)^m; unlimited expected attempt work is μ/θ.The unlimited result assumes an infinite sequence of independent draws.Source: §C.1 · p. 60

C.2.1. Reducing work with a short program

  • For horizon T, direct cellular-automaton simulation costs Θ(T^2), while a fixed shortcut computes the same output in Θ(T) work.The shortcut scans the input window and combines its endpoint bits; discovering the routine is a separate acquisition task.Source: §C.2.1 · pp. 60–61

C.2.2. Cumulative deepening

  • In the prefix-parity history, inherited state computes each next task in two transitions, versus n + 1 from the original state, satisfying the cumulative-deepening criterion.Earlier tasks retain the accumulator and head position used by later tasks.Source: §C.2.2 · p. 62

C.2.3. Finite search for work-reducing routines

Finite search can acquire a retained routine that reduces total work on a bounded training family. The search has explicit scope limits, and preserving capability across participant replacement is a related but distinct concern.

C.2.3. Finite search for work-reducing routines

  • Finite search exhaustively evaluates candidate fields and emits a minimising state; if its total work is strictly below baseline, it reduces work on at least one evaluated task.The construction guarantees termination through an exhaustive baseline and counts candidate execution, checking, and encoding work.Source: §C.2.3 · pp. 62–63
  • Minimising total training-task work can increase work on an individual task, while the guarantee concerns only the fixed procedure and training tasks.The restricted search can establish weak grasp dominance at input bound zero, not optimality outside the bounded retained-state class or task family.Source: §C.2.3 · p. 63
  • A length-penalised search can find a global minimiser by evaluating a finite code-length range after computing baseline work.The bound is determined by baseline work divided by the positive rational penalty γ.Source: §C.2.3 · p. 63

C.3. Preserving capability

  • Preserving capability through participant replacement requires a checkpoint whose functions later work depends on; switching results bound its length and production work.The checkpoint must preserve those functions despite replacement.Source: §C.3 · p. 64

C.3.1. Maintaining capability

A two-copy system illustrates how shared storage and participant memory can preserve a capability through turnover or deletion, provided each run has enough work for restoration.

C.3.1. Maintaining capability

  • With both copies, emitting the stored word costs k + c; with either single copy, restoring the missing copy raises the run cost to 2k + c.Losing both copies makes the target unattainable at input bound zero.Source: §C.3.1 · p. 64
  • At least 2k + c work per run lets one remaining copy answer and restore the other, preserving capability across arbitrarily many participant replacements.The k-work gap is implementation-relative.Source: §C.3.1 · p. 64
  • Under turnover alone, emitting the shared copy without restoration costs k + c, but later deletion of that shared copy leaves no copy.The variant persists under turnover but not the combined turnover-and-deletion disturbances.Source: §C.3.1 · p. 65
  • Removing a component without changing performance does not locate the capability, because another stored copy or procedure may preserve it.Source: §C.3.1 · p. 65

C.3.2. Replacing components

The switching construction separates direct adoption, function-preserving continuation, and function-preserving migration. When required responses are unavailable after switching, preserving them can require work proportional to the information that must be carried over.

C.3.2. Replacing components

  • Keeping the response table externally available can permit a constant-size routing checkpoint, but continued access to that resource still incurs horizon costs.Source: §C.3.2 · pp. 66–67
  • A preserving switch has a checkpoint-length lower bound C(z_R | T, R, y_B) − O(log(T + 2)); when all T responses are required, migration takes Θ(T) work.The lower bound applies to any replacement checkpoint that must provide the required responses.Source: §C.3.2 · pp. 65–66
  • With every response required, continuation under A costs O(1) acquisition work, preserving a switch to B costs Θ(T), and a direct B switch costs O(1).Before development, choosing either architecture costs the same O(1) work.Source: §C.3.2 · p. 66
  • A copying procedure gives an O(T)-work upper bound for preserving the required responses by copying their table into a B checkpoint.The checkpoint then answers the required queries within the stipulated service-work bound.Source: §C.3.2 · p. 67

C.3.3. Short descriptions under query work limits

Short descriptions need not provide query service within a work limit: feasibility depends on the checkpoint and persistent resources available. The construction separates the cost of acquiring information from the cost of switching while preserving service.

C.3.3. Short descriptions under query work limits

  • With external state yA = zT, a constant-size A-routing checkpoint answers all T queries within BT; with yB = ε, every valid B checkpoint needs at least ⌊T/2⌋ bits.Source: §C.3.3 · p. 68
  • Function-preserving migration to a B checkpoint costs Θ(T), while continuation and direct switching use constant work.Source: §C.3.3 · p. 68
  • The constructed response table zT has constant description complexity given T, yet no B checkpoint shorter than ⌊T/2⌋ answers every query within BT work.Source: §C.3.3 · p. 68
  • The lower bound applies even to short generators and compatibility programs because the B interpreter includes a general program mode.Source: §C.3.3 · p. 68

C.4. Comparing organisational arrangements

Organisational resources can reduce task work, but establishing coordination may itself require work. The examples quantify both persistent-role savings and the trials needed to discover suitable worker assignments.

C.4. Comparing organisational arrangements

  • In the reporting example, immediate exchange takes 18 operations per task, while retained roles take 13; random proposals have positive expected savings only for horizons H ≥ 7.Source: §C.4 · pp. 69–70
  • For this instruction table, retained roles require 13 work per task versus 18 without organisation, while a pooled routine takes 5 operations and Tcoord = 8.Source: §C.4 · p. 70
  • Without communication—including shared state, timing, and termination signals—no fixed isolated implementation succeeds on all four input pairs.Source: §C.4 · p. 70
  • When all n roles are required (m=n), acquisition depth is at least n(n−1)/2 trials at every margin; replacing k workers in the freed roles takes worst-case k(k−1)/2 trials.Source: §C.4 · p. 70
  • Testing possible workers for each required role in turn attains the worst-case trial count m(2n−m−1)/2.Source: §C.4 · pp. 70–71

C.5. Evaluating success

The section distinguishes work needed to attain a score from whether success under that score matches the intended target. It constructs demanding evaluators and relates evaluator choice to the work measured by depth.

C.5. Evaluating success

  • At a fixed input bound, restricting accepted responses cannot reduce required work, but changing the accepted set can also change depth’s description-based input bound.Source: §C.5 · p. 71
  • For one system–state pair, a finite-description graded task can make level n require more than Tn work at margin s while keeping Cτdem(n | x) ≤ K + ℓ(n).Source: §C.5 · p. 72
  • One finite-description evaluator gives every enumerated system–state pair depth above Tn for each margin s once n ≥ max{i, s, 1}.Source: §C.5 · p. 73
  • When the system can execute reference programs with fixed input overhead and the margin covers that overhead, the constructed depths are finite and, for an unbounded schedule, tend to infinity with the required level.Source: §C.5 · pp. 73–74

C.6. Recursive improvement

A search index built during one search can lower the work of later searches, making successive states more capable and their own improvements cheaper. The section also gives a fixed interpreter for improvement procedures whose code changes over time.

C.6. Recursive improvement

  • Each index-building round weakly grasp-dominates the preceding state on the domain tasks at every finite work budget.Source: §C.6 · p. 75
  • Rounds 1 through d−1 satisfy the self-contribution condition and form a finite instance of recursive improvement with positive recursive gain.Source: §C.6 · p. 75
  • The work reduction comes from the index built in that round: removing its first division makes the next round’s work rise while it still meets the target.Source: §C.6 · p. 75
  • A fixed interpreter reproduces each admissible changing procedure, with stage work bounded by one fixed polynomial in the stated input, state, output, and transition quantities.Source: §C.6 · p. 76
Loading 2610.38728v1…