Jump to text
On this page
Copy and source
Published source confirmed at last check

Source changed 2026-11-16 21:18:08 UTC · snapshot created 2026-11-16 21:19:40 UTC · last check 2026-11-17 19:15:10 UTC

CMP.Reference:1.1 - A description specifies a family of possible processes

Distinguish a computational description from an execution. A description gives rules for operations, choices, state change and interaction under a computational model. An execution is one process admitted by those rules with particular inputs and environmental behavior. The same finite description can admit indefinitely many inputs and executions. It can describe a calculation that returns, a generator that yields further values, or a service that remains available for events. A nondeterministic schedule or random choice can admit several executions even for one input.

This distinction makes an algorithmic guarantee possible and limits it. A guarantee concerns an admitted family, not just the trace that was inspected. One test can expose a counterexample; a general claim needs an argument appropriate to that family. Conversely, a failure outside the admitted conditions does not establish a failure within them, although it may show that the conditions do not serve the actual work. CMP.1 transfers obtainability or a limit only through its justified conversion; CMP.11 derives a resource limit from what every allowed computation must distinguish.

An effective operation is available at a stated level. Comparing two bounded words, evaluating a supplied function, requesting a remote result and choosing a mathematically existing witness are not interchangeable primitives. If a needed operation is missing, its name is a construction obligation. Another algorithm may implement it, a physical system may supply it under qualified conditions, or no suitable means may yet be known. C.29.2 develops that formulation and returns to it when the proposed operations do not obtain the required answer.

The recipient determines the relevant observations. A final number can suffice for one calculation. Another use needs an attaining object, the order of emitted events, an error, an exception, termination, or continued responsiveness. An abstract step can correspond to several implementation steps, but a correspondence that ignores visible intermediate behavior can fail in an interacting context. CMP.12 develops the execution meaning; CMP.14 handles consequential interaction. Keeping those observations explicit prevents a successful value calculation from being mistaken for the required whole behavior.