We Query, Therefore We Compute: On Oracle Computation beyond the Machine, with an Application to Agents

• The practical-machine construction begins by asking which Oracle to use.Source: Extended Abstract · p. 1

1.1 Two Clouds over Agentic Systems

• Prior work treats questions such as caching from separate perspectives and lacks a shared foundation for specifying an agentic operating system’s guarantees or unifying Workflow and Agent mechanisms.Agent builders view the cache as reusable task context, while model servers view it as attention-state KV cache.Source: §1.1 · p. 2

1.2 One Instruction, Two Symmetry Breakings

• For internally autoregressive Oracles, cache state forms a hierarchy from history to KV cache; under stated conditions, append-only histories compute each token once, while missing return times can double keep-or-discard cost.The hierarchy’s excess recomputation equals what re-encoding the history discards.Source: §1.2 · pp. 4–6, §1.4 · p. 7
• For every Oracle, the safety boundary fixes where content crosses into Priestess control, but no such guarantee fixes which content crosses.The boundary is not a defense against prompt injection.Source: §1.2 · pp. 4, 6, §1.4 · p. 7

1.3 ArchNights

• ArchNights extends RV64 with an Oracle mode and instruction, and its Linux-style PRTS kernel returns control at one fixed entry and confines ordinary tasks.Its system library uses semantic delegation to move work from Oracle history into the kernel.Source: §1.3 · p. 6
• ArchNights-SE performs comparably to mini-swe-agent and Terminus 2 on Terminal-Bench 2.1 with the same model and setting.The evaluation uses deepseek-v4.1-flash; ArchNights-SE also produces a music video given virtual display and audio output.Source: §1.3 · p. 6

1.2 One Instruction, Two Symmetry Breakings

• The O-2-PDA adds an instruction that sends a whole stack to a black-box Oracle and appends its answer, while two stacks support Turing-complete Priestess computation.When a program only appends to a stack, its history grows autoregressively, like an agent’s context.Source: §1.2 · p. 3, §1.4 · p. 6

1.4 Contributions

• The paper’s three-part contribution is the O-2-PDA, its derived operating-system contract and task placements, and construction V’s von Neumann realization.The contract, placements, and safety boundary require none of the three named assumptions; the prototype has no refinement proof or security guarantee.Source: §1.4 · pp. 6–7

1.2 One Instruction, Two Symmetry Breakings

• Storage and transition breakings make a Priestess program the operating system for Oracle tasks, with an every-Oracle contract and Agent and Workflow as two program placements.The contract confines a task to its own stack and returns control only at a fixed entry; with a budget, control also returns on a good machine.Source: §1.2 · pp. 3–4, §1.4 · p. 6

1.4 Contributions

• For an overview, readers are directed to skim §§2.4–2.5, read §3, §§4.2–4.3, §§5–6 with Appendix D, and then Appendices E.6–E.7.Source: §1.4 · p. 7
• For building agents, readers are directed to §§2.5 and 3.5, the statements of §4 results, Table 10, and Appendix E.Source: §1.4 · p. 7
• For safety, readers are directed to §§3.4, 4.4, and 5.2, and Appendices C.10, E.4, and E.6.Source: §1.4 · p. 7
• For human–computer interaction and automated systems, readers are directed to §§3.4–3.5 and the discussion of a person as an Oracle in §5.4, then Appendix E.5.Source: §1.4 · p. 7

2.1 Two-Stack Pushdown Automata, Written as Programs

• A two-stack pushdown automaton is Turing-complete because its stacks can represent a Turing machine’s tape on either side of its head.The program-style form represents finite control as numbered instructions and the state as a program counter.Source: §2.1 · p. 7

2.2 Split Stacks and Their Colours

• Splitting physical stacks into logical stacks preserves other stacks during each operation, while their P and O colours initially serve only as labels.A finite block of steps realizes each logical-stack operation and restores the other logical stacks.Source: §2.2 · pp. 8–9

2.3 The Oracle and Its Instruction

• The Oracle instruction submits a whole stack through an encoder and decoder, then appends one possible answer to that same stack; rejected queries jump to a label.The model assumes answers are non-empty; a real Oracle is total only if every accepted query receives a non-empty answer in finite time.Source: §2.3 · pp. 9–10

2.4 What the Instruction Adds

• With a deterministic Oracle, the O-2-PDA and an oracle Turing machine compute the same partial functions; the instruction adds the form of appending each answer to its query.The comparison assumes the same Oracle; the oracle Turing machine may also ask whether a word lies in the encoder’s domain.Source: §2.4 · p. 10

2.5 The Autoregressive Form

• When accepted queries recur on a stack and intervening operations only push to it or test it, each next query contains the previous history, Oracle answer, and program pushes.The Oracle answer comes from applying O to the entire preceding history; program pushes act as interjections, and the form belongs to the interaction rather than the Oracle’s internal process.Source: §2.5 · p. 10

3.1 Data and Thunks: a CBPV Fragment

• CBPV distinguishes stored data from computations that run, giving the machine a vocabulary for reading the same stack content as either an Oracle program or data supplied to a computation.The fragment is used for semantic analysis; the two readings share an instruction that appends the answer to its operand.Source: §3.1 · pp. 11–12

3.2 Storage Symmetry Breaking S

• S makes Priestess-stack Oracle calls return data, while only Oracle stacks may hold programs for the Oracle to run; S changes content readings, not machine runs.Priestess instructions may still read and write either stack colour.Source: §3.2 · p. 12

3.3 Transition Symmetry Breaking T

• T gives execution distinct P- and O-modes: the Priestess chooses when and on which Oracle stack a task runs, while the Oracle’s yield ends the excursion at a fixed trap label.The minimal breakings preserve both task-program placements; their contract holds for every program and run.Source: §3.3 · pp. 12–13

3.4 The Kernel Contract

• For every Oracle, program, and run, an excursion appends answers only to its entered stack, reads only that stack, returns only at the trap label, and leaves answers as data to Priestess code.Together, K1 and K2 provide spatial isolation; K3 and K4 prevent answers from becoming code addresses or instructions.Source: §3.4 · pp. 13–14
• Content crosses from O-mode to P-mode only through the trap’s force of the service code, and from P-mode to O-mode only after the Priestess writes a stack and enters it with uret.The crossing invariant follows from the excursion’s stack locality and the transition rules.Source: §3.4 · pp. 14–15
• On a good machine, a budget makes every excursion trap within β O-mode transitions while preserving K1–K4; without a budget, O-mode tasks are scheduled cooperatively.The budget bounds transitions, not elapsed time, and preemption is no finer than one O-mode transition.Source: §3.4 · p. 15
• A Priestess program acts as the operating system when it enters task stacks with uret and serves their traps at the fixed service entry, allowing it to schedule tasks and handle requests.The operating system comprises a kernel and a library that declares the kernel’s services to tasks.Source: §3.4 · pp. 15–16
• S identifies where task programs reside, while T determines privilege; the kernel contract guarantees storage and control boundaries for every Oracle, with control return under a budget on a good machine.Kernel scheduling and services are outside this machine-level contract and require separate verification.Source: §3.4 · p. 16

3.5 Agents and Workflows on One Machine

• Agent form places the task program in Oracle-side history served by the kernel; Workflow form places it in Priestess code that calls the Oracle for data.Oracle output becomes part of the Agent’s program by default, whereas a Workflow must explicitly interpret or promote returned data to program content.Source: §3.5 · pp. 16–17
• Hybrids combine Agent and Workflow program parts; ordinary model–tool harnesses exhibit Agent form, while a scaffold is the system library and programs available to a task.Agent parts use kernel-mediated yield-and-return interactions, while Workflow parts use P-mode calls and data binding.Source: §3.5 · pp. 17–18
• A Priestess-side interpreter reproduces Agent tasks’ queries and answers without uret; conversely, a compiler can run Workflows as Agent tasks while preserving their effects on Priestess stacks.The reverse translation supports K1–K4, and K5 when the kernel enters tasks with budgets on a good machine.Source: §3.5 · p. 17
• Form and paradigm are distinct: prompt chaining is Workflow form and paradigm, orchestrator-workers is Workflow form with the Agent paradigm, and autonomous agents are Agent form and paradigm.Either implementation form can realize either paradigm with a suitable compiler.Source: §3.5 · pp. 17–18
• S and T are the unique color assignments that preserve both Agent and Workflow placements while preventing P-mode calls from reading answers appended in O-mode.The criterion requires both placements to exist, remain apart, and hold for every program and Oracle without conditions on the program.Source: §3.5 · p. 18

4.1 Encoder and Decoder, Step and Frame

• When the encoder factorizes at the yield symbol, histories synchronize at Frame boundaries; the Oracle’s own history matches the machine’s encoding there exactly when it is Frame-faithful.The encoding never backs up across a Frame boundary, though the two histories can diverge within the current Frame.Source: §4.1 · p. 20
• Decoded Frames need not reveal how many internal Steps an Oracle took; Frame-faithfulness makes the Step count derivable from the decoded Frame and encoder.Without Frame-faithfulness, internal transitions are not observable through the Frame interface unless additional metadata, such as a Step count, is exposed.Source: §4.1 · p. 21

4.2 Two Caches, One Hierarchy

• A state cache models Oracle prefix reuse alongside Priestess storage in one hierarchy, matching transformer KV-cache hits and prefill rematerialization without changing the machine’s executions.For a transformer, one state transition corresponds to one token of prefill or decode; cache tiers in host memory and storage sit below the KV cache.Source: §4.2 · p. 22
• A state cache’s excess recomputation is bounded by the encoder’s loss, and factorization at the yield symbol eliminates recomputation at Frame boundaries.If the encoding grows by at most one symbol, the bound is the loss plus one; at a Frame boundary, the cost is the encoding length of the extension.Source: §4.2 · p. 23
• With factorization at ♮, a Frame-faithful Oracle, and kernel pushes ending in ♮, each later query extends the encoded history by the kernel’s push alone.A private state cache then makes later queries cost only |E(v)|, where v is the push since the last Frame, and computes each encoded symbol once.Source: §4.2 · p. 23
• Cache reuse follows an append-only epoch: Agent queries chain under the kernel’s epoch discipline, while Workflow calls chain when the program never pops its Priestess stack.Rewriting a task stack starts a new epoch; a Frame that does not re-encode to itself can require recomputation beyond the push.Source: §4.2 · p. 24

4.3 Two Schedulers

• The Priestess-side scheduler chooses which task to enter and for how long, while the Oracle-side scheduler orders Oracle computations; the Priestess knows next keys, but the Oracle knows its cache.The task’s return time is decided on the Priestess side and is not determined by the Oracle’s queries or answers.Source: §4.3 · pp. 24–25
• 2 is the minimum worst-case cost ratio for a deterministic retention policy without return-time knowledge, attained exactly at θ = R/µ.Every policy pays at least opt(T) = min(µT,R), while a policy knowing T can attain it.Source: §4.3 · p. 25

4.4 Safety: the Boundary

• The safety boundary fixes where content enters and leaves each computation: the Priestess writes operands, answers return at a trap or call, and gates govern content-dependent control.The theorem holds for every Oracle; whether crossings are checked depends on the code.Source: §4.4 · pp. 25–26
• No guarantee that holds for every Oracle can exclude a chosen answer at a call; it can fix the crossing boundary, but not which content crosses.The proposition permits an Oracle with the same codec to append any non-empty decoded answer at a reachable call; excluding it requires a codec property.Source: §4.4 · p. 26
• In Agent form the boundary lies in the kernel; in Workflow form it lies in the program’s operands and answer-reading code, where validation is the program’s responsibility.A hybrid has a boundary for each part, and moving a task between forms moves its boundary.Source: §4.4 · pp. 26–27

5.1 Who Is the Oracle?

• V runs only internally autoregressive Oracles in O-mode, while P-mode can call any Oracle; wrapping can make a machine good without changing an Oracle’s internal autoregression.The wrapper works under the stated alphabet and yield-symbol conditions, but iteration can lose meaning or fail to represent the Oracle’s own transition.Source: §5.1 · p. 28

5.2 Memory: Stacks as Segments

• Stacks become disjoint memory segments, and bounded Oracle appends preserve stack contents while ensuring each Oracle step writes only within its operand’s segment or writes nothing.An append that exceeds the segment’s capacity is refused; the kernel may grow the segment, end the task, or compress context.Source: §5.2 · pp. 28–29
• The fetch condition forbids fetching instructions from any segment an Oracle rule can write, separating Oracle-written data from executable code.Priestess code may choose computed jump targets or write code itself; the restriction concerns where instructions are fetched from.Source: §5.2 · p. 29

5.3 Control: One Instruction, No Code

• The physical machine makes the Oracle operation one instruction: O-mode runs no code of its own, while P-mode calls the same instruction like any other.O-mode queries the task segment, appends the answer, and traps on a yield or exhausted budget; the operation is atomic at the interface.Source: §5.3 · pp. 29–30

5.4 Oracle-Priestess’s Message

• An O-mode yield is a system call to the Priestess, and a return supplies its reply; semantic delegation lets the Priestess compute a requested value without adding the computation’s definition or intermediate steps to history.The packed operator must provide the services of the calls it replaces, though the history may be shorter.Source: §5.4 · pp. 30–31
• A person is usually called in P-mode, whereas an internally autoregressive language model may run in O-mode under the paper’s assumption.Running a person in O-mode requires a declared mechanism of generation.Source: §5.4 · p. 31

6 ArchNights: Implementation on gem5

• ArchNights-SE prototypes the machine in gem5 syscall-emulation mode, while ArchNights-FS remains an unbuilt, unvalidated design; both share an instruction set and distribution.They differ in their kernels, PRTS and ZOOT, respectively.Source: §6 · p. 31

6.1 What ArchNights Keeps of the Machine

• ArchNights defines realization obligations for machine-fixed behaviors but claims no simulation between the implementation and the abstract machine.Oracle-operation faults are absorbed as traps that leave the store unchanged, preserving K1–K4 and allowing K5 to hold without the good-machine hypothesis.Source: §6.1 · pp. 31, 33

6.2 The Instruction Set

• ArchNights adds Oracle mode, uret, and an Oracle instruction with STEP, RUN, and PROBE operation granularities and capabilities.uret enters a task using its stack, budget, and Oracle entity; the budget is checked at STEP or FRAME boundaries, and RUN-only Oracles can be preempted only between frames. Operations are synchronous, though asynchrony may be implemented behind the abstraction if a task is not in O-mode on two processors at once.Source: §6.2 · p. 34

6.3 PRTS: the Kernel of ArchNights-SE

• PRTS represents a process as an Oracle history paired with Priestess-side state, and schedules tasks from a ready queue with Oracle-step budgets.Fork copies the history and creates a result channel; checkpointing can compress a history’s middle at a quiet point, but breaks the prefix chain and invalidates caches keyed by the old history.Source: §6.3 · pp. 35–36

6.4 The Distribution

• The distribution’s system library exposes operators through semantic delegation calls, while its shell combines an Oracle-driven task with a Priestess-side session.The session receives user input as data and writes it into the task history; programs run as child tasks isolated from the shell.Source: §6.4 · pp. 36–37

6.5 ZOOT: the Kernel of ArchNights-FS

• ZOOT is a design for running alongside Linux, with a separate U-mode kernel for each user and Linux in S-mode as arbiter.The U-mode kernels share some Priestess-side state, with operations on that shared state requiring higher privilege.Source: §6.5 · p. 37

6.6 Evaluation of ArchNights-SE

• ArchNights-SE scores 77.5–83.1 Pass@1; mini-swe-agent scores 80.9 and Terminus 2 scores 78.7 with the same model and setting.The minimal system scores 77.5 with its default prompt and 83.1 with an extra prompt; the full system scores 77.5 with its default prompt.Source: §6.6 · pp. 37–38
• With the same model, mini-swe-agent scored 80.9 in this evaluation versus DeepSeek’s 90.3, though the harnesses align in kind, not strictly in score.DeepSeek reported 84.1–90.6 across eight configurations in its own settings; the paper cannot attribute the 9.4-point difference because DeepSeek does not report its harness prompts.Source: §6.6 · p. 38
• ArchNights-SE ran a music-video task as both an agent harness carrying it through and a general-purpose computer running programs on its devices.The ordinary user oracle reached the host through bash, with each call routed through sodo; the task played its score through fb_play, a semantic delegation call registered in a kernel module.Source: §6.6 · p. 38, Figure 7 · p. 39

7.1 Other Foundations for Agentic Systems

• Unlike agent operating-system analogies that place the model as resource, kernel, or computer, this machine derives placements from the ordering of storage and transitions.In the Agent form, the Oracle processes the task program and the Priestess acts as its operating system.Source: §7.1 · pp. 39–40

7.2 Agents and Harnesses

• Agent and Workflow are placements of a task’s program, distinct from the paradigm of whose output directs the next step.The harness literature’s two poles—model-authored code and deterministic control flow—map to these forms, while planned graphs can be Workflows in form and Agents in paradigm.Source: §7.1 · p. 40, §7.2 · p. 43

7.1 Other Foundations for Agentic Systems

• Its guarantees ensure every request reaches the policy code, while whether that code consults policy and what it decides remain properties of the kernel.This replaces per-check mediation assumptions with the assumption that a realization faithfully implements the machine.Source: §7.1 · p. 41

7.3 Theory of Computation

• The O-2-PDA persists interaction history on a stack, queries with the whole stack, and lets the Oracle run its own program in O-mode until a trap returns control.With a deterministic Oracle it computes what an oracle Turing machine with that Oracle computes; the paper’s results do not depend on whether interaction adds power beyond Turing machines.Source: §7.3 · p. 44
• The machine combines whole-stack Oracle calls, a contract derived from stack-color symmetry breaking, and a von Neumann layout; the authors report no known precedent for this combination.Its two stacks make it Turing-complete, and ArchNights provides one Oracle instruction with a mode below user mode.Source: §7.3 · p. 45

7.4 Programming Languages

• The paper uses a simplified call-by-push-value fragment to name stored data and executable content, and its Agent–Workflow pairing is not a computational duality.The fragment keeps shifts U and F and ground type D, omitting other types and the calculus’s metatheory.Source: §7.4 · p. 45

7.5 Operating Systems and Computer Architecture

• Definition 3.8 specifies what makes one program another’s operating system, leaving management to its code; unlike library operating systems, ArchNights delegates abstractions from Oracle history into the kernel.This reverses the usual move of placing abstractions in applications because the costly crossing on this machine is the Oracle round trip.Source: §7.5 · p. 45
• S restricts stored content’s right to run according to its stack’s colour, while T makes privilege a transition mode; complete mediation is enforced by trapping every return to the Priestess.The paper distinguishes privilege between the two sides from information-flow control, whose labels and constraints differ.Source: §7.5 · p. 46
• The machine’s rules give it the virtualization property that sensitive instructions trap, while kernel isolation, kernel sharing, and supervisor-level principals represent different placements of operating systems and arbitration.The contract holds across these placements; isolation among users inside the Priestess remains the arbiter’s responsibility.Source: §7.5 · p. 46
• Unlike verified-kernel work that proves code against a written specification, this paper derives a contract from machine rules; kernel correctness and service policy remain properties of each kernel.A kernel for the O-2-PDA-TS could be verified using existing methods, with the machine-provided contract forming part of its specification.Source: §7.5 · p. 46
• ArchNights builds on the von Neumann architecture, RISC-V’s privileged architecture, and Rocket Chip’s RoCC interface, leaving other Priestess computation to an ordinary processor.The RISC-V xRET instruction is followed to enter O-mode.Source: §7.5 · p. 46

7.6 Inference Systems and Agent Safety

• A separator synchronizes the processes at each Frame boundary only when the Oracle is Frame-faithful, called through the Frame interface, and kernel writes end with ♮.The synchronization grounds the cache results; §4 adds a use for encoder theory rather than a new theory.Source: §7.6 · p. 46
• Serving systems share and page KV caches, while program-aware servers schedule calls by their programs; the paper states these mechanisms against its machine model.Reuse beyond prefixes falls outside the §4 model, compaction and paging start a new epoch, and schedulers are classified by which side they belong to and schedule.Source: §7.6 · p. 46
• The safety boundary fixes where a monitor mediates crossings and leaves policy to the kernel; it does not inspect the Oracle’s answer or itself defend against prompt injection.The contract covers provenance-mediated crossings, not whether a request is the right one; defenses can act on the way in, inside the Oracle, or on the way out.Source: §7.6 · p. 47

8 Conclusion

• The O-2-PDA adds one Oracle instruction to a two-stack machine; symmetry breakings S and T derive an operating system, while construction V fits the machine to a von Neumann computer.ArchNights demonstrates that the computer construction can be built and serve as the basis of an agent harness.Source: §8 · p. 47
• The machine’s kernel contract is an invariant, and Agents and Workflows are two placements of a task’s program.Source: §8 · p. 47
• Open work spans machine metatheory and complexity, safety under concurrency, prototype extensions, and empirical questions about language models.The listed questions include isolation among users, finite capacity, non-autoregressive Oracles, and whether semantic delegation helps.Source: §8 · p. 47
• AgentNights is proposed as the next step: implementing the machine, kernel, and system library in host software without a simulator.The authors offer the machine as a place to accumulate understanding through design choices argued from invariants and bounds for both system forms.Source: §8 · p. 47

A Glossary and Notation

• The glossary distinguishes storage stacks and their colours from element types and execution modes, and defines the operating system as a kernel plus system library.A type marks stored elements as data or suspended programs; a mode specifies whether Oracle answers or Priestess code chooses the next transition.Source: A Glossary and Notation · p. 63

B Proofs

• The stack-rearrangement block simulates an instruction on a logical stack and restores the other stacks; its Oracle extension restores the tape after accepted calls or rejection.Each rearrangement handles a finite prefix, so it takes finitely many steps.Source: B Proofs · p. 63

C More on Eclipse

• The appendix gathers additional material on encoders, hierarchies, stores, cache coherence, prefix chains, schedulers, and safety analysis.Source: C More on Eclipse · p. 64

C.1 Encoders

• BPE with a proper dictionary has finite Step backtrack, but an encoder with longest-match tokenization can have unbounded backtrack even with two symbols.A single appended a can lose m symbols in the stated example.Source: §C.1 · p. 64

C.2 Composing Hierarchies

• A hierarchy views a function through its memos; connecting systems adds a key-translation level, while recursion composes memoized functions into a hierarchy.A miss pays the chain’s cost only through the first memo that hits.Source: §C.2 · p. 65

C.3 The Stores of the Two Sides

• The Oracle’s cache is keyed by histories and can rematerialize misses through prefill, while the Priestess’s CPU-style store is keyed by addresses and generally lacks rematerialization.Source: §C.3 · p. 65

C.4 Coherence of the Encoding Cache

• An encoding-cache entry can encode only the appended suffix while the stack grows, but a non-append write must invalidate or otherwise verify that entry.The state cache already holds generated states, whereas the encoding cache reads and encodes the decoded answer at each call.Source: §C.4 · p. 66

C.5 The Prefix Chain in the Two Forms

• The prefix chain is a machine invariant within an append-only Agent epoch, but a property of program text in Workflow form.Source: §C.5 · p. 66

C.6 The Two Schedulers in More Detail

• The Oracle scheduler handles linked sequences of computations, and cache reuse depends on whether history grows at Step, Frame, or intermediate granularity.The Priestess scheduler estimates residency and access costs to use cache affinity.Source: §C.6 · p. 66
• At Frame granularity, the state cache holds the earlier history, so the next query costs only what the kernel pushed since the prior Frame.At Step granularity, the history is re-encoded and the state cache recomputes up to the Step backtrack; for BPE with a proper dictionary, that backtrack is finite.Source: §C.6 · p. 66
• The reuse analysis is for one task on one Oracle with a private cache; finite-capacity sharing across tasks can evict state, making the stated reuse an upper bound.Source: §C.6 · p. 66

C.7 A Budget Trap inside a Frame

• A budget trap inside a Frame can leave a history that is not Frame-faithful, so Proposition 4.10 does not cover that case.The Oracle may hold the state of a generated token while the history encodes its decoded text differently.Source: §C.7 · p. 66

C.8 Where Non-empty Answers and Frame-Faithfulness Hold

• For internally autoregressive Oracles, non-empty answers follow through the Frame interface, while the Step interface requires that no generated symbol decode to an empty string.Byte-level tokens that contain only the beginning of a multi-byte character can violate the condition when machine-side symbols are characters.Source: §C.8 · p. 66
• Without non-empty answers, yield-versus-budget detection and the interpreter’s answer-top test need extra bookkeeping, while repeated empty queries can prevent progress until a budget ends the excursion.The prefix-growth and no-return properties also fail; K5 does not use the convention.Source: §C.8 · p. 67
• Frame-faithfulness for a language model requires canonical generated tokenizations, retention of every generated token by the decoder, and reuse of the same tokenizer without answer rendering.Sampling, decoding, and rendering can each break the property.Source: §C.8 · p. 67
• A budget trap inside a Frame is outside the completed-Frame conditions, so Proposition 4.10 does not cover its possible mismatch between the Oracle’s state and the encoded history.Source: §C.8 · p. 67
• When Frame-faithfulness fails, the next query’s extra recomputation is bounded by the re-encoding of the last Frame and does not persist beyond that query.Under Proposition 4.10’s stated hypotheses and private-cache condition, a never-Frame-faithful Oracle still generates each answer once and prefills its re-encoding at most once.Source: §C.8 · p. 67

C.9 Reasoning: Kept, Dropped or Hidden

• Reasoning may be kept, dropped by a decoder or encoder, removed by the kernel, or hidden in an opaque block, with different effects on history and reuse.Kept reasoning can preserve Frame-faithfulness; decoder- or encoder-dropped reasoning breaks it and incurs recomputation, while kernel removal is a rewrite whose cost depends on where it begins. Hidden blocks preserve reasoning only under codec-specific conditions; partial validation, Oracle-specific blocks, and authenticated encryption limit what the machine models.Source: §C.9 · p. 68

C.10 Protection, Channels and Attacks

• Protection restricts Oracle access to storage, while a task’s possible histories change only through Priestess writes and scheduling.Scheduling is a control channel and kernel writes are the content channel; clock-reading code can add cache-latency channels outside the model. Replay requires repeated queries, possible after a kernel rewrite or an Oracle failure; non-empty answers make an Agent’s queries strictly grow within an epoch.Source: §C.10 · p. 69

D.1 The Instruction Set in More Detail

• The Oracle instruction encodes PROBE, STEP, or RUN in a custom-0 R-type instruction, and realizations can hide its latency in hardware or by scheduling other tasks.The result reports status, steps, and published answer bytes; asynchronous execution preserves synchronous semantics, with single-task-at-a-time execution required as a scheduler invariant in a multiprocessor kernel.Source: §D.1 · pp. 69–71

D.2 More on PRTS

• Linux fork copies the parent’s address space and descriptor table, while inherited descriptors share open files and their offsets.The child receives copied working-directory, credential, and signal-disposition state, but has a new identifier and starts resource accounting at zero.Source: §D.2 · p. 71

D.3 Exceptions of an Oracle Unit and in PRTS

• PRTS handles Oracle-unit exceptions by retrying recoverable errors, backing off from encoder errors, and resampling after decoder errors.If an answer exceeds segment capacity, the kernel enlarges the segment and retries; if an answer is cut off before yielding, it backs off the unfinished answer and retries, unless an interactive user decides instead.Source: §D.3 · pp. 71–72

D.4 Communication and System Calls in PRTS

• PRTS uses Unix communication mechanisms, but content enters a task history only through explicit, bounded reads by that task.Fork connects parent and child through a result channel by default, and the Oracle holds no pipe end; internal system calls are kernel functions not exported to O-mode by default.Source: §D.4 · p. 72

D.5 More on the Distribution

• PRTS exposes intent-oriented operators that replace lower-level system-call sequences, while keeping descriptors, pipes, and wait ordering inside the kernel and system library.A history records the Oracle’s continuation and kernel-returned values, not kernel code; shell events become one-line inputs, while programs’ terminal output is not recorded in history.Source: §D.5 · pp. 72–73

D.6 ZOOT

• ZOOT adopts kernel-sharing for U and S users, shares task identifiers across O- and P-modes, and reuses the U address space for O-mode Oracle stacks.Because O-mode has no virtual addresses of its own, large Oracle stacks require advance reservation in U-mode; lazy page commitment limits the cost.Source: §D.6 · p. 73
• ZOOT can use discretionary access control or virtualize O-mode filesystems; its layered boot targets an O-mode program, and its Linux bridge is designed to avoid intrusive changes.With separate users and kernels, each user can have a separate O-mode filesystem, with some files shared.Source: §D.6 · p. 73

E.1 Encoders

• BPE’s finite lookahead, determined by its dictionary, bounds its Step backtrack, while incremental tokenization extends the encoding as history grows.BPE also has a deterministic automaton and an incremental algorithm that maintains the tokenization of every input prefix [246] [247].Source: §E.1 · p. 75
• When a prompt ends inside a token, the machine treats it as a history ending inside a Frame; factorization at ♮ keeps the loss there, while other prefix-chain breaks may require repair.The passage also identifies budget traps inside a Frame and encodings that do not re-encode to themselves as other breaks in the prefix chain.Source: §E.1 · p. 75
• Encoder results extend to autoregressive vision-language-action Oracles when their action tokenizer satisfies the results’ hypotheses, as must be checked for each tokenizer.Examples include RT-2 text action tokens [95], OpenVLA discretized action tokens, and FAST’s compressed action chunks [252].Source: §E.1 · p. 75

E.2 Caches

• In Agent form, histories share prefixes through kernel forks or restores; in Workflow form, programs push shared prefixes, and append-only task queries extend one tree path.Reuse follows encoded-prefix agreement; at a Frame boundary it adds no encoder loss when the encoder factorizes at ♮.Source: §E.2 · p. 75
• For append-only conversations, retaining state means each turn computes only newly appended symbols once; tiered caches transfer state instead of dropping it.The model treats prefill as computing Priestess-written symbols and decode as computing Oracle-generated symbols.Source: §E.2 · p. 76
• A history rewrite starts a new epoch: its first query reuses the nearest cached prefix, while later queries extend the rewritten history.A sliding window can make every query an epoch’s first; Workflow compaction is visible in program text, whereas Agent rewrites follow runtime policy.Source: §E.2 · p. 76
• Reuse beyond prefixes falls outside the model; retaining states after an edited or removed span does not preserve states of the new history as Definition 4.8 defines them.The passage identifies CacheBlend, Prompt Cache, CachedAttention’s truncation, and Leyline’s span edits as outside that definition.Source: §E.2 · p. 76

E.3 Scheduling

• Within an append-only epoch, the last Frame’s device has the task’s whole history, so its next query costs only the intervening push; migration costs more as history grows.While that device’s cache remains resident, longer-running agents weigh cache affinity more heavily against load balance.Source: §E.3 · p. 76
• Prefix paths link queries only within an append-only epoch; task identifiers are needed across rewrites and to distinguish tasks with identical histories.ArchNights carries the task identifier on every Oracle operation.Source: §E.3 · p. 77
• During a tool call, keeping, discarding, or swapping Oracle state adds different costs to the next query; return timing is known on the Priestess side, not from Oracle queries.No deterministic policy lacking return-time knowledge stays within less than twice the cost of an informed policy; the stated time-to-live R/µ is also within twice.Source: §E.3 · p. 77
• Agent-form Priestess scheduling chooses task, timing, and slice, while Workflow programs can delegate concurrent calls to handlers without changing script logic.Step-counted slices require exposed Oracle steps, and STEP can end inside a Frame; RUN-only preemption occurs between Frames. The passage also reports a tenfold Tree-of-Thoughts speedup for a handler.Source: §E.3 · p. 77

E.4 Safety

• On the way in, a filter sees all content entering a task only if it covers initial content and every record the kernel builds.Defenses may block content or mark it for the Oracle; marking works only together with a defense inside the Oracle.Source: §E.4 · pp. 77–78
• Inside the Oracle, defenses receive the inputs written on the way in, but the machine cannot certify which requests the Oracle will pass.The answer relation depends on the Oracle’s history, and strong adversarial attacks remain a risk.Source: §E.4 · p. 78
• In the Agent form, every request reaches the kernel at the service entry; in the Workflow form, untrusted content reaches control through program gates.CaMeL’s strict mode adds branch conditions or loop iterables as dependencies of variables assigned within them.Source: §E.4 · p. 78
• A harness can promote tool-result content into a privileged record, making the escalation a fault of kernel writes rather than a crossing around the boundary.An input defense sees promoted content only if it covers every record the kernel builds.Source: §E.4 · p. 78
• The boundary locates crossings but does not prove noninterference, cover outside channels, or establish that a defense’s decision is correct.It is one component of a security argument, not the argument itself.Source: §E.4 · pp. 78–79

E.5 Privilege Reversed

• With privilege reversed, the Oracle is privileged and mediates tasks running in P-mode; task code runs confined, while the Oracle decides at traps.The arrangement parallels the machine’s account of automated systems and human-computer interaction, with the privileged side exchanged.Source: §E.5 · pp. 79–81
• K1–K5 confine tasks to their own stacks, restrict reads to those stacks, route control through traps and dispatches, and return control to the kernel within a bounded segment.Requests reach the Oracle as input to a decision, never as the decision itself.Source: §E.5 · p. 80
• The reversed contract holds for every Oracle, but it cannot verify the trusted party’s judgment or that its decisions are good.For a person acting as Oracle, the task code is confined, but the person may never decide; trust must be assumed or measured.Source: §E.5 · p. 80
• Human-automation checks become conditions on the Oracle’s decisions, which the contract cannot state; a request that steers a privileged language-model Oracle is a prompt injection.The paper therefore places an untrusted language model below the Priestess rather than in the privileged Oracle role.Source: §E.5 · p. 81
• An interpreter can implement the reversal with P-mode calls and system-call code; an approval gate combines a person above the Priestess and the Priestess above the model.That chain has two Oracles of different classes and trust, which neither machine formalizes alone.Source: §E.5 · p. 81

E.6 Black-Box Confinement

• S’s colour designation does not distinguish runs, while T’s privilege designation corresponds to distinct machines with the same K1–K5 contract and reversed roles.The two task-program placements and two assignments of privilege form four combinations; an operating system occurs when the task and trusted party are on different sides.Source: §E.6 · pp. 81–82
• A safe program never uses the same stack for a uret operand and a P-mode Oracle call; this decidable condition suffices for K1–K4 and the crossing boundary for every Oracle.Safety is a program condition, unlike goodness, which is a codec condition.Source: §E.6 · p. 82
• Safety is weaker than S because it constrains operands rather than stack colours, and the boundary can fail only when a P-mode call reads content an excursion appended.Removing P-mode Oracle calls makes the boundary hold without a safety condition, but removes the Workflow form.Source: §E.6 · p. 82
• A realization whose confined side executes instructions must supply isolation, a fixed entry, control over what crosses back, and a bound on its execution.These mechanisms supply K1–K5; a base fixes the entry and treats the confined party only as data, but cannot fix which content reaches it.Source: §E.6 · pp. 82–83

E.7 Several Levels of Privilege

• Ordinary privilege levels resemble the machine’s layering, but user mode executes its own instructions, unlike the Oracle side, which runs no instruction of its own.On a realization with an Oracle, the Oracle mode is added below user mode.Source: §E.7 · p. 83
• The one-Oracle contract applies at an individual level, not to a tower as a whole; the tower needs a separate theorem that this paper does not provide.An approval gate is another nesting arrangement, combining two Oracles rather than stacking privilege levels.Source: §E.7 · pp. 83–84

E.8 Oracles and the Lynchpin Hypothesis

• World models and vision-language-action models may fit O-mode, while diffusion models and usually people are called in P-mode; whether they meet the machine’s hypotheses remains open.A diffusion-native runtime rewrites Priestess content between calls, outside the append-only epochs described for the machine.Source: §E.8 · p. 84
• Evidence on long-context and tool-call performance is consistent with the Lynchpin hypothesis, but does not prove it; call by name shortens history while increasing declaration size.Whether this trade pays depends on a model of the Oracle’s answers.Source: §E.8 · p. 84

E.9 Applications and Extensions

• For embodied agents, every actuator command can be treated as a P-mode request, letting a Priestess-side check inspect commands before they reach the motors.The boundary applies only if the Priestess is the sole publisher to actuators; the paper also identifies different Oracle classes and asynchrony as open items.Source: §E.9 · p. 85
• On BIG-Bench Hard, Chain of Code scored 84 with interleaved execution and emulation, 63 with emulation, 57 with emulation plus a state trace, and 48 with Python alone.The paper frames program-based reasoning as a program the Priestess evaluates, while whether semantic delegation improves correctness remains open.Source: §E.9 · p. 85
• Separating code and language models maps to multiple Oracles chosen by the Priestess, while a program written by whichever Oracle runs only when the Priestess executes it.The multiple-Oracle machine remains an open item.Source: §E.9 · p. 85
• Learned prefetch can serve a predicted request before the task makes it, but speculative requests must avoid effects and disclose no intent beyond the task’s own request.Handling effects and the feedback loop from learning on one’s own traces remain design concerns.Source: §E.9 · pp. 85–86