Computability Boundary Mapping¶

Before optimizing or automating a problem, determine whether any correct terminating procedure can solve the declared class, prove that boundary, and publish a weaker but honest fallback when it cannot.

Summary¶

Before optimizing or automating a problem, determine whether any correct terminating procedure can solve the declared class, prove that boundary, and publish a weaker but honest fallback when it cannot.

Engineering effort cannot produce a total exact algorithm for a class that has none, while a theorem about an unrestricted class need not forbid useful restricted tools. Map the in-principle boundary first, then place every practical method and public claim on the correct side of it.

The first question in an automation project is not “Which algorithm should we implement?” It is “Does an algorithm with the promised guarantee exist for this entire class under the capabilities we are willing to assume?” That question precedes optimization, scaling, staffing, and interface design. A team can spend years improving code for a specification that no total procedure can satisfy, or abandon a useful problem because one search timed out. This archetype prevents both errors by tying every conclusion to a precise problem, representation, model, quantifier, guarantee, and proof.

Computability Boundary Mapping is therefore both analytical and architectural. It classifies the in-principle boundary, but it does not stop at a theorem. It maps decidable fragments, one-sided recognizers, bounded solvers, proof-carrying paths, approximations, assisted modes, and abstention behavior. The output is a truthful operating contract: what the system can always decide, what it may eventually confirm, what it can only approximate, what depends on an external capability, and what remains unresolved or impossible in general.

The structural problem¶

A project assumes that every sufficiently precise question can be turned into a total algorithm, or treats repeated implementation failure as proof that no algorithm can exist. The problem class, input encoding, computational capabilities, universal quantifiers, and required guarantee are left implicit. As a result, teams may pursue impossible universal automation, mislabel an expensive but computable problem as undecidable, present one-sided search as a decision procedure, or cite an impossibility theorem whose assumptions do not match the deployed system.

The root tension is: Users want universal, exact, terminating answers, but the expressive power needed to state the problem can make such answers unavailable in principle; useful operation therefore requires a transparent trade among scope, expressiveness, completeness, termination, approximation, and assistance.

Several distinctions must survive the analysis. Uncomputable does not mean slow. Slow does not mean impossible. No known algorithm does not mean no algorithm exists. A successful run does not establish a total procedure. A timeout does not establish a negative answer. A proof checker does not necessarily generate proofs. An unrestricted impossibility result does not erase decidable sublanguages or bounded cases. The archetype exists to keep these boundaries explicit under design pressure.

Intervention logic¶

Name the exact decision, function, enumeration, synthesis, or verification problem and define valid inputs and outputs.
Fix a finite representation and interpretation for instances, outputs, equality, and translations.
Declare the computation model, including permitted interaction, randomness, advice, external data, oracles, and resource semantics.
State the required guarantee across soundness, completeness, exactness, totality, uniformity, and termination.
Make universal quantifiers, promise conditions, domain bounds, and class-versus-instance scope explicit.
Seek a constructive procedure witness and verify both correctness and termination over the declared class.
In parallel, test whether a known undecidable source reduces to the target or whether diagonalization, theorem instantiation, or another proof rules out the requested guarantee.
Review reduction direction, model equivalence, and theorem assumptions independently before changing the classification.
Assign the strongest justified status: total computable/decidable, one-sided recognizable, partial, relative, undecidable/uncomputable, or unresolved.
Map useful decidable subclasses and identify which restrictions on language, state, input promise, precision, or size recover totality.
Choose a fallback that truthfully changes the contract: restrict scope, expose unknown, use bounded approximation, accept certificates, add interaction, escalate, or decline.
Publish the classification, evidence, lost guarantees, operational timeout semantics, and triggers that require reanalysis.
Only after computability is established, perform complexity and practical feasibility analysis for the constructive procedure.

The sequence deliberately separates four questions. First, what is the formal problem? Second, what computational power and guarantee are being claimed? Third, what evidence establishes the strongest justified status? Fourth, what should the system do when the original status is weaker than users requested? A reduction can settle the third question without answering the fourth. A useful fallback can answer the fourth without changing the theorem. A mature design needs both.

Parallel evidence search is important. Constructive work and impossibility work should not be treated as ideological camps. An explicit terminating algorithm defeats an overbroad impossibility claim for the specified class. A sound reduction defeats endless attempts to satisfy an impossible universal requirement. When neither side succeeds, the honest result is unresolved, together with a research and operating plan—not a forced declaration.

Key components¶

Component	Description
Problem-Class Specification ↗	Defines the family of instances, the exact question or function, valid inputs, required outputs, and the distinction between solving one instance and solving every instance in the class. Computability is a property of a precisely stated mapping or decision problem under a model, not of a topic label. The specification should state whether the output is Boolean, constructive, enumerative, optimizing, or explanatory; identify promise conditions; and make malformed inputs explicit.
Instance Representation Contract ↗	Fixes how problem instances and outputs are finitely encoded, interpreted, compared, and translated between representations. A representation can hide infinite precision, a non-effective oracle, or undecidable semantic equivalence. Encoding changes must be computable and meaning-preserving before a reduction or constructive procedure is accepted.
Computation Model Contract ↗	Declares the allowed operations, information access, interaction pattern, randomization, advice, oracle calls, and termination semantics of the effective procedure being considered. An impossibility result is always relative to a model and assumptions. Quietly adding an oracle, an unbounded human judgment step, real-number exactness, or nonuniform advice changes the claim rather than defeating it.
Solvability Guarantee Profile ↗	States which combination of soundness, completeness, exactness, totality, uniformity, and termination is required. Many useful tools are sound but incomplete, complete only on a promise class, probabilistic with bounded error, or partial. The profile prevents a recognizer, heuristic, bounded search, or approximate method from being marketed as a total decider.
Quantifier and Scope Map ↗	Makes explicit whether the claim covers every valid input, almost all inputs, one bounded size, one distribution, one formal language, or one named instance. The difference between “this instance was solved,” “every instance up to size n is solvable,” and “one uniform procedure solves the unbounded class” is central. Universal quantifiers and hidden promise conditions must be visible.
Computability Status Lattice ↗	Records the strongest justified status: total computable or decidable, one-sided recognizable, partial, relative to an oracle or interaction model, undecidable or uncomputable, or unresolved. The status is a lattice of evidence and guarantees, not a binary slogan. “Unresolved” is required when neither a constructive procedure nor a sound impossibility proof is available.
Constructive Procedure Witness ↗	Provides an explicit effective procedure together with correctness and termination arguments for the declared problem class and model. Examples, benchmarks, or successful runs are not enough for a universal claim. The witness must cover all allowed branches and inputs, and its representation assumptions must match the specification.
Reduction Preservation Contract ↗	Specifies the computable translation, direction, and property preservation needed to transfer solvability or impossibility between problem classes. Reduction direction errors are common and fatal. To prove a target at least as hard as a known undecidable source, the source must reduce to the target; the reverse direction establishes something different.
Computability Impossibility Certificate ↗	Carries a checkable reduction, diagonal construction, theorem instantiation, or other proof that no procedure with the required guarantee can exist under the declared model. A timeout, failed implementation, high complexity, or absence of a known algorithm is not a certificate. The proof must state its assumptions and the exact guarantee it rules out.
Assumption Register ↗	Tracks semantic, representational, computational-model, theorem, and environment assumptions on which the classification depends. Reuse the indexed component. Assumptions should be versioned and linked to the conclusions they support so later changes trigger reclassification rather than silent guarantee drift.
Decidable Subclass Map ↗	Identifies restrictions, bounded domains, finite-state fragments, promise conditions, or parameter regimes that recover a total effective procedure. A general undecidability result rarely means every useful case is hopeless. The map must state which restriction restores solvability and what coverage or expressiveness is lost.
One-Sided Recognition Contract ↗	Defines which side of a yes/no problem receives a terminating certificate or recognizer and what happens on the other side. For a recognizable but undecidable problem, positive instances may eventually be confirmed while negative instances can run forever. The interface must expose that asymmetry rather than treating delay as a negative answer.
Unknown and Nontermination Policy ↗	Governs timeout, abstention, cancellation, partial progress, resource caps, and the public meaning of an unknown result. Operational systems need a finite response even when the underlying procedure may not terminate. A timeout is an operational event, not a theorem; the policy must preserve the epistemic distinction.
Fallback Solution Contract ↗	Selects a safe response when the original total-exact requirement is unachievable: restrict scope, accept one-sided recognition, approximate with bounds, request a certificate, add interaction, escalate, or decline the task. The fallback must restate the new guarantee and avoid presenting a weaker method as if it solved the original class. Safety-critical systems need explicit behavior for out-of-scope and unknown cases.
Computability Guarantee Record ↗	Publishes the problem definition, model, classification, evidence, restrictions, termination behavior, known unknowns, and permitted claims for users and downstream systems. This record prevents theorems from being detached from their assumptions and prevents partial or bounded tools from inheriting stronger language than their evidence supports.
Recheck Trigger ↗	Initiates reclassification when the input language, representation, computation model, allowed interaction, guarantee, or domain restriction changes. Reuse the indexed component. A change that adds an oracle, bounds the domain, weakens completeness, or expands the language can change the computability result even when the product name remains unchanged.
Termination Condition ↗	Defines the observable halt states and completion semantics of a constructive procedure or bounded fallback. Reuse the indexed component. For a decider it must be reached for every valid input; for a recognizer it may be guaranteed on only one side, which must be stated.
Scope Boundary ↗	Marks the exact input and environment region to which the classification and guarantee apply. Reuse the indexed component. Runtime detectability matters when out-of-scope inputs must be routed to abstention, review, or a different method.
Decision Record ↗	Documents why the selected classification and fallback were accepted, including rejected interpretations and unresolved objections. Reuse the indexed component. It is especially important when formal conclusions alter product promises, public eligibility, or safety claims.
Uncertainty Residue ↗	Preserves questions not settled by the proof, including model mismatch, encoding uncertainty, theorem applicability, and open classification status. Reuse the indexed component. A clean theorem can coexist with uncertainty about whether a real system satisfies its premises.
Independent Proof Review ↗	Assigns a qualified independent reviewer to verify reductions, theorem assumptions, model equivalence, and public guarantee language. High-consequence claims should not depend on the same author who designed the specification or benefits from an impossibility conclusion.
Complexity Follow-On Gate ↗	Routes a problem proven computable to resource-scaling, approximation, architecture, or optimization analysis before deployment. Computability answers whether some effective procedure exists in principle; it does not establish practical latency, memory, energy, data, or coordination cost.

Common mechanisms¶

Constructive Algorithm and Correctness Proof¶

Exhibits a uniform procedure and proves that it returns the required answer and terminates for every valid instance in scope.

Many-One Reduction Proof¶

Maps each instance of a known source problem to one target instance while preserving the answer, transferring decidability or undecidability in the justified direction.

Turing-Reduction Analysis¶

Tests whether solving one problem with permitted calls to another would decide the source problem, making oracle access and adaptivity explicit.

Diagonalization Impossibility Proof¶

Constructs an input or object that defeats a claimed total analyzer through controlled self-reference or enumeration escape; intended as the mechanism destination for queue position 26.

Halting-Problem Reduction¶

Shows that a proposed universal analyzer would decide program halting, thereby ruling out the analyzer under the declared general-purpose computation model.

Enumeration and Dovetailing¶

Interleaves potentially nonterminating searches so every finite successful branch eventually receives attention, supporting recognizers and enumerable result sets.

Semi-Decision with Explicit Unknown¶

Runs a one-sided recognizer under an interface that distinguishes confirmed, still-searching, timed-out, cancelled, and unresolved states.

Bounded-Domain Exhaustive Search¶

Enumerates a finite declared domain to provide total answers inside that bound without claiming a uniform unbounded solution.

Promise-Problem Restriction¶

Restricts valid inputs to a stated property under which a total solver exists and rejects or abstains when the promise cannot be established.

Language-Fragment Restriction¶

Limits expressiveness, recursion, quantification, state, or data types to a decidable fragment with a published coverage loss.

Theorem-Prover-Guided Search¶

Searches for formal derivations or countermodels and returns proof objects where possible, while retaining explicit incompleteness or nontermination behavior.

Abstract Interpretation or Model Checking¶

Computes sound abstractions or explores bounded/finite-state models to decide selected properties for a restricted system class.

Reduction-Direction Checklist¶

Checks source, target, computability of the translator, preservation condition, theorem assumptions, and the exact conclusion before a reduction is accepted.

Computability Boundary Decision Record¶

Captures the final classification, evidence, assumptions, fallback, public wording, and recheck conditions in a reviewable artifact.

Fallback-Mode Router¶

Routes inputs or requests to a decider, recognizer, bounded solver, approximation, certificate path, human escalation, or abstention according to the declared boundary.

Proof Checking¶

Independently verifies a constructive proof, reduction, diagonal argument, or machine-produced certificate before the classification changes system behavior.

Proof by Counterexample¶

Refutes a claimed universal correctness or termination property for a proposed procedure; it does not by itself prove that no different procedure could work.

Computational Complexity Analysis¶

After computability is established, estimates how time or space grows and whether the constructive procedure is practically tractable.

No individual mechanism is the archetype. A reduction can be correct but applied to the wrong formalization. A theorem prover can be useful but incomplete. A model checker can be total only for the finite-state model it actually receives. A timeout can protect service availability but says nothing about logical impossibility. Mechanisms must be assembled around the full specification–model–guarantee–evidence–classification–fallback loop.

Parameter dimensions¶

Problem form¶

Decision, function computation, enumeration, synthesis, optimization, verification, equivalence, or property analysis.

Instance class¶

Finite named set, bounded size, recursively generated class, all programs in a language, all formulas in a logic, or a promise class.

Representation¶

Strings, graphs, programs, formulas, exact integers, rational approximations, finite-state machines, streams, or interactive transcripts.

Computation model¶

Deterministic, nondeterministic, randomized, interactive, distributed, oracle-relative, human-assisted, or physically constrained.

Guarantee¶

Soundness, completeness, exactness, bounded error, totality, uniformity, eventual recognition, certificate verification, or best effort.

Termination semantics¶

Always halts, halts on positive cases, halts under a promise, halts within a bound, may run forever, or is externally cancelled.

Evidence class¶

Constructive proof, reduction, diagonal argument, theorem instantiation, machine-checkable certificate, counterexample, empirical search, or unresolved analysis.

Scope restriction¶

Language fragment, finite state, bounded recursion, bounded input size, bounded precision, restricted topology, fixed parameter, or certified promise.

Fallback mode¶

Unknown, abstain, approximate, bounded search, certificate request, assisted decision, deferred batch processing, or refusal.

Operational stakes¶

Convenience, financial allocation, security, safety, legal rights, scientific inference, or infrastructure control.

Reclassification trigger¶

New language feature, new oracle, representation change, revised guarantee, larger domain, theorem update, or discovered counterexample.

Parameter choices are not cosmetic. Adding unrestricted recursion can move a language across a decidability boundary. Requiring both soundness and completeness while preserving termination can turn a useful analyzer into an impossible specification. Allowing a certificate can make verification easy without making generation total. Bounding instance size can recover exhaustive decidability while leaving the unbounded class unchanged. Every classification should therefore be read as a function of these parameters, not as a permanent label attached to a topic.

Invariants and outcomes¶

Invariant: Semantic fidelity: the analyzed formal problem still represents the real task being claimed.
Invariant: Model transparency: every extra source of computational power or information is declared.
Invariant: Evidence soundness: constructive and impossibility conclusions follow from checkable arguments under stated assumptions.
Invariant: Reduction direction correctness: hardness and impossibility are transferred only in the justified direction.
Invariant: Status honesty: decidable, recognizable, partial, relative, undecidable, and unresolved are not collapsed.
Invariant: Complexity separation: in-principle solvability is not confused with resource feasibility.
Invariant: Fallback fidelity: weaker methods do not inherit the original total-exact claim.
Invariant: Operational safety: unknown and out-of-scope inputs have explicit non-deceptive behavior.
Invariant: Traceability: model, guarantee, evidence, restrictions, and public language are version-linked.
Outcome: Impossible universal automation requirements are rejected or narrowed before large implementation commitments.
Outcome: Constructive algorithms are accompanied by class-wide correctness and termination obligations rather than only benchmarks.
Outcome: Undecidability claims are tied to valid reductions or theorem assumptions rather than analogy.
Outcome: Recognizers, bounded analyzers, and approximations expose their exact guarantee and unknown behavior.
Outcome: Decidable fragments are designed intentionally with measurable expressiveness and coverage loss.
Outcome: Users and downstream systems can distinguish false, unknown, timeout, out-of-scope, and impossible-to-decide-in-general.
Outcome: Computable problems move to complexity and architecture assessment with the right practical questions.
Outcome: Changes in language, model, or external capability trigger reclassification instead of silent guarantee drift.

A successful deployment preserves a three-layer truth. The mathematical layer states what is provable under the formal model. The engineering layer states what the implementation can do under resource and reliability constraints. The user-contract layer states what outputs mean and what happens outside the proven region. Many failures occur because a statement from one layer is copied into another without qualification.

Recognized variants¶

Decision-Problem Decidability Mapping¶

Classifies whether a yes/no problem has a correct procedure that terminates on every valid input, with recognizability and complement behavior recorded when total decision fails.

Distinctive feature: The result space is explicitly Boolean, so total decision can be separated cleanly from one-sided recognition and complement recognition.

Why it remains under the parent: It uses the same representation, model, quantifier, constructive-witness, reduction, impossibility, and fallback structure.

Semi-Decision and Recognizability Mode¶

Uses a one-sided terminating recognizer while preserving an explicit unknown or still-searching state for the side that lacks a guaranteed halt.

Distinctive feature: Nontermination is part of the contract rather than an implementation defect hidden behind an arbitrary timeout.

Why it remains under the parent: It is selected only after the same computability boundary analysis and uses the same guarantee and scope records.

Restricted-Domain Computability Recovery¶

Recovers total solvability by narrowing the language, state space, input promise, recursion depth, numeric representation, or instance size to a decidable fragment.

Distinctive feature: The intervention changes the problem class itself and makes the restriction part of the public contract.

Why it remains under the parent: The restriction is justified and maintained by the parent’s status, evidence, fallback, and recheck logic.

Relative or Interactive Computability Analysis¶

Reclassifies solvability relative to declared oracle access, interaction, human input, external measurement, or trusted advice rather than silently treating those capabilities as free computation.

Distinctive feature: The computational power and failure behavior of the external source become explicit parts of the model.

Why it remains under the parent: The same boundary mapping is rerun under a changed computation model and guarantee profile.

The variants are status and response patterns, not separate theorem names. A particular theorem, language, or tool can instantiate several variants depending on its declared class and guarantee. The same analyzer might be a total decider on a finite-state fragment, a sound incomplete recognizer on a larger language, and an unresolved heuristic on inputs outside its model.

Tradeoffs¶

Expressiveness versus decidability: richer languages state more problems but may lose total analysis guarantees.
Completeness versus termination: a terminating sound analyzer may need to return unknown or miss valid cases.
Scope versus usefulness: narrowing to a decidable fragment can make a tool honest but exclude important real cases.
Exactness versus bounded approximation: a weaker result may be operationally valuable if error and abstention are controlled.
Autonomy versus external assistance: oracle, expert, sensor, or certificate access can recover relative solvability while adding dependency and governance risk.
Formal proof effort versus decision stakes: rigorous classification can be expensive, but unsupported universal claims are costly in high-consequence systems.
Uniformity versus specialization: one general procedure is easier to govern, while instance-specific advice may hide nonuniform or non-effective assumptions.
Theoretical generality versus runtime detectability: a clean promise class is useful only when membership can be established or conservatively enforced.
Transparent unknown versus forced decisiveness: abstention preserves truth but may impose delay, human workload, or unequal service.

The central design trade is often expressiveness versus total analyzability. A more expressive language lets users state more relationships and behaviors, but it may make universal static questions undecidable. Removing expressiveness can restore a total procedure, yet can also push real complexity into extensions, external services, or manual review. The archetype does not prescribe “always restrict.” It requires the restriction and its burden to be explicit.

Another trade is completeness versus service finality. An incomplete but terminating analyzer can safely return unknown; a complete search may need unbounded time. Operational systems frequently prefer a bounded response, but that preference does not change theorem status. The design must choose whether to preserve truth through abstention, preserve coverage through potentially unbounded search, or introduce an approximation with a different error contract.

Failure modes¶

Timeout mistaken for undecidability¶

Cause: A search or solver exceeds an operational resource limit.

Mitigation: Label timeout as an operational unknown, inspect complexity and implementation, and require a proof before claiming no total procedure exists.

Computable mistaken for tractable¶

Cause: Existence of an algorithm is treated as evidence that it can meet real latency, memory, energy, or cost constraints.

Mitigation: Route every constructive result through Complexity Scaling Assessment and practical validation.

Reduction direction reversal¶

Cause: The target is reduced to a known hard problem when the intended conclusion requires reducing the known hard problem to the target.

Mitigation: Use the reduction-preservation contract and independent direction checklist with explicit source, target, translator, and conclusion.

Model inflation after an impossibility result¶

Cause: An oracle, expert, exact real-number operation, unbounded advice string, or external database is added without changing the claim.

Mitigation: Version the computation model, classify the assisted result as relative, and specify availability and correctness of the added capability.

Class-versus-instance confusion¶

Cause: Success on one instance or all cases up to a tested bound is generalized to an unbounded uniform algorithm.

Mitigation: Keep the quantifier and scope map attached to every result and state finite bounds prominently.

One-sided recognizer sold as a decider¶

Cause: Positive cases eventually terminate, while unresolved negative cases are hidden behind a timeout.

Mitigation: Implement the one-sided recognition contract and expose confirmed, unresolved, cancelled, and timed-out states.

Theorem-assumption mismatch¶

Cause: A famous impossibility theorem is cited for a different language, fault model, representation, oracle, or guarantee.

Mitigation: Instantiate assumptions line by line and preserve unresolved status when equivalence is not proved.

Overrestriction to regain decidability¶

Cause: The system removes so much language, state, or input coverage that it no longer solves the user’s real problem.

Mitigation: Measure excluded cases, publish expressiveness loss, and provide an escalation path for legitimate out-of-fragment inputs.

Unknown collapsed into false¶

Cause: Interfaces, metrics, or incentives require a Boolean answer even when the method cannot decide.

Mitigation: Make unknown a first-class state with downstream handling rules, service-level semantics, and audit metrics.

Proof checker confused with proof generator¶

Cause: Cheap certificate verification is assumed to imply cheap or guaranteed certificate discovery.

Mitigation: Separate generation and verification roles and cross-reference the later verifier-prover-asymmetry target.

Representation smuggles in non-effective power¶

Cause: Inputs assume exact infinite objects, semantic equality, or an uncomputable encoding oracle.

Mitigation: Require finite effective encodings and computable meaning-preserving translations.

Unresolved research question reported as impossible¶

Cause: No algorithm or impossibility proof is currently known.

Mitigation: Use the unresolved status, document evidence gaps, and set a recheck trigger.

Impossibility used to evade accountability¶

Cause: An organization cites uncomputability to avoid improving a bounded or approximate process that is feasible.

Mitigation: Map decidable subclasses and bounded fallbacks, and independently review whether the theorem actually blocks the requested operational improvement.

Two meta-failures deserve special attention. The first is theorem laundering: a project invokes a famous impossibility result to make a local design choice appear mathematically compelled even though the assumptions differ. The second is implementation laundering: a practical timeout, classifier threshold, or human escalation rule is presented as if it resolves the underlying computability question. Both are prevented by the same discipline—keep model, guarantee, evidence, and fallback in separate named records.

Neighbor distinctions¶

Heuristic Vs Algorithm Tradeoff And Selection¶

That archetype chooses among available practical decision methods based on stakes, speed, error, and cost. Computability Boundary Mapping asks whether any method with the requested total guarantee exists for the declared class.

Complexity Scaling Assessment¶

Complexity Scaling Assessment studies time, space, or coordination growth of a procedure. This archetype precedes it by separating existence of an effective procedure from the resources it requires.

Bounded Approximation¶

Bounded Approximation is a fallback for expensive or unavailable exact solutions. It does not prove computability or undecidability and must state how its error guarantee differs from the original contract.

Proceduralization¶

Proceduralization turns tacit work into explicit steps. A written procedure may still fail to terminate, depend on non-effective judgment, or lack a universal correctness guarantee.

Deductive Chain Validation¶

Deductive Chain Validation checks whether a proof follows. Proof checking can support this archetype, but it does not classify the existence of a total solver or proof generator.

Counterexample Search¶

Counterexample Search refutes a proposed universal algorithm or proof claim by finding one failure. It does not show that every possible procedure must fail.

Self Referential Paradox Detection And Resolution¶

That archetype repairs self-application loops and paradoxes. Diagonalization may use self-reference as an impossibility mechanism, but computability boundaries also arise through reductions and model limitations without a paradox-repair intervention.

Constraint Propagation And Decoupling¶

Constraint propagation reduces search spaces and decomposes problems. It can improve a computable method or recover a subclass, but it does not establish the class-wide effective-procedure boundary.

Bounded Search Pruning¶

Bounded Search Pruning makes finite search practical by eliminating branches. A bounded search can be total inside its declared bound without deciding the unbounded class.

Incompatible Requirement Set Resolution¶

The prior queue draft handles a set of commitments with no joint model. A specification can be consistent and define a meaningful relation while still admitting no total effective procedure for all instances.

Assumption Bounded Distributed Agreement¶

The prior consensus draft uses domain-specific impossibility and conditional liveness results. It is an application neighbor, not the general parent for computability classification.

Regress Termination Rule¶

Regress Termination Rule chooses a justified stopping point for inquiry. It does not guarantee that an algorithm halts on every instance or prove an undecidability boundary.

Independent Verification Oversight¶

Independent Verification governs who checks evidence and outputs. It can validate a computability proof but does not supply the classification logic.

System Scope Definition¶

System Scope Definition draws boundaries around a system. This archetype uses scope as one input and may narrow it to recover decidability, but adds model-relative solvability proof and status semantics.

The most important boundary is with complexity. A computable problem may require astronomically large resources; an undecidable problem has no total effective procedure at all under the model. Complexity reductions and undecidability reductions can use similar notation, but their conclusions differ. The quality report and guarantee record should state which kind of boundary is being claimed.

The boundary with inconsistent requirements is equally important. A problem relation can be coherent and nonempty yet uncomputable as a total mapping. Conversely, a finite constraint set can be efficiently checked and still have no satisfying assignment. One asks whether a model exists; the other asks whether a uniform effective procedure can produce the required answer for every instance.

Examples¶

Universal program termination analysis¶

A team proposes a service that accepts any program and input and always returns whether execution will halt. Tests, bounded simulation, and timeouts are useful operationally but cannot support the universal total claim. A validated halting-problem reduction supplies an impossibility certificate for the unrestricted language. The team then defines restricted languages with structural termination guarantees, bounded execution analyzers, and a proof-carrying path. The product’s output vocabulary includes terminates, does not terminate within a declared bound, proof verified, unknown, and out of supported fragment. None of these operational labels is allowed to masquerade as the impossible unrestricted decider.

Theorem search with proof verification¶

A proof system can enumerate candidate derivations and quickly verify a valid proof. If the target statement is a theorem, search may eventually find a proof; if it is not, search may continue indefinitely. The service therefore offers one-sided recognition, resource-bounded search, and independent proof checking. It does not call every search timeout a disproof. Where a decidable fragment exists, the router moves those formulas to a total procedure.

Decidable query-language fragment¶

A query platform wants expressive recursion, external predicates, and guaranteed termination. Boundary mapping shows that unrestricted combinations defeat the total guarantee. The platform defines a decidable core, requires external predicates to meet finite response contracts, statically rejects unsupported recursion, and routes advanced queries to a sandbox with explicit timeout and partial-result semantics. The restriction is visible in documentation and machine-readable schemas.

Finite-state verification boundary¶

A model checker exhaustively explores a finite transition system and returns a total answer for the property. When users add unbounded queues, dynamic process creation, or unbounded data, the original finite-state guarantee no longer applies. The model contract and recheck trigger force a new classification. Abstraction may recover sound results with unknown; it is not described as the same complete finite-state decision.

Certificate-based synthesis¶

A synthesis service cannot guarantee it will find a valid controller whenever one exists, but it can verify a supplied controller and certificate efficiently. The architecture separates candidate generation from proof checking, exposes unresolved search, and accepts external certificates. This is relative and one-sided operation under the current parent; the later verifier-prover-asymmetry archetype can own the cost-separation design in greater depth.

Formal policy engine with expert escalation¶

A policy engine decides ordinary cases inside a stratified rule fragment. Cases with unrestricted cross-references or open-text judgment are not forced through the decider. They move to an expert channel whose authority, response time, refusal, and appeal behavior are explicit. The engine is total only relative to the restricted formal fragment; the combined service is an assisted workflow with a separate external-capability contract.

Non-examples¶

Benchmarking two known sorting algorithms on larger inputs.
Writing a standard operating procedure for a manual approval process.
Choosing a heuristic because an exact optimizer misses a latency target.
Resolving mutually inconsistent safety, cost, and performance requirements.
Debugging one program that happens not to terminate.
Calling a model inaccurate because the training distribution shifted.
Using a proof checker to validate a supplied certificate without claiming certificate generation is total.

Practical review questions¶

What is the exact problem class, and is the claim about one instance, a bounded family, or every valid instance?
How are inputs and outputs finitely represented, and are translations effective and meaning-preserving?
What computational powers, external sources, randomization, interaction, or advice are permitted?
Which guarantees are required: soundness, completeness, exactness, totality, uniformity, and termination?
What constructive algorithm and proof support a positive classification?
What reduction, diagonal argument, theorem, or certificate supports a negative classification?
Has the reduction direction and theorem-assumption match been independently checked?
Is the result decidable, one-sided recognizable, partial, relative, undecidable, or unresolved?
Which restrictions recover a useful decidable subclass, and can those restrictions be enforced?
What does timeout mean, and can users distinguish false, unknown, cancelled, out-of-scope, and service failure?
What weaker fallback is offered, and how is its changed guarantee communicated?
After computability is established, what complexity and practical feasibility questions remain?
Who bears the cost of abstention, scope restriction, or human escalation?
What changes to language, representation, model, or guarantee trigger reclassification?

Computability Boundary Mapping succeeds when it prevents both impossible promises and premature surrender. It gives theorem-level limits an operational form, while preserving the design space inside, around, and relative to those limits. Its final product is not merely a label such as “undecidable.” It is a governed map of what can be guaranteed, under which assumptions, for which inputs, with which evidence, and what the system must do everywhere else.

Common Mechanisms¶

Abstract Interpretation or Model Checking — Decides a property soundly on a finite abstraction of an otherwise-undecidable system, trading exactness for a guaranteed answer that never misses a real violation.
Bounded-Domain Exhaustive Search — Turns a question that is undecidable in general into a decidable one by fixing a finite bound and mechanically checking every case inside it.
Computability Boundary Decision Record — Records where a project drew the computability boundary, which guarantee it will ship, and what would force the line to be redrawn.
Computational Complexity Analysis — Once a problem is known solvable in principle, measures how its cost grows with input size to place it in a complexity class and separate the tractable from the merely computable.
Constructive Algorithm and Correctness Proof — Settles a problem on the decidable side by exhibiting an actual algorithm and proving it both total and correct — the proof and the procedure are one object.
Diagonalization Impossibility Proof — Proves that no algorithm can decide a class by constructing, from any candidate decider, a self-referential input on which it must be wrong.
Enumeration and Dovetailing — Semi-decides a class by fairly interleaving all candidate computations, halting 'yes' the moment one succeeds and otherwise running on — buying a complete yes-side at the cost of no honest 'no'.
Fallback-Mode Router — Dispatches each query to the strongest method that fits where it falls relative to the computability boundary — exact, sound-approximate, bounded, or escalated — under an explicit fallback contract.
Halting-Problem Reduction — Proves a target problem undecidable by wiring a known-undecidable problem (canonically the halting problem) into it, so effort on a universal solver stops before it starts.
Language-Fragment Restriction — Regains a terminating decision procedure by narrowing the language problems are stated in to a syntactic fragment known to be decidable, trading expressive power for a guaranteed answer.
Many-One Reduction Proof — Transfers a problem's decidability or hardness verdict along a single total computable map that preserves membership, exhibiting the mapping itself as the proof.
Promise-Problem Restriction — Makes a hard problem solvable by narrowing the inputs the solver is accountable for to those meeting a stated promise, leaving promise-violating inputs as don't-cares.
Proof by Counterexample — Refutes an over-broad universal claim — that some method handles an entire class — by exhibiting one well-formed instance on which it demonstrably fails.
Proof Checking — Independently re-verifies a decidability or impossibility proof step by step, so the boundary claim rests on a checked argument rather than on its author's authority.
Reduction-Direction Checklist — A pre-flight check that a reduction runs from the known-hard problem into the target — the direction that actually proves hardness — with every assumption named before the verdict is trusted.
Semi-Decision with Explicit Unknown — Runs a sound one-sided recognizer that confirms YES when it can, but returns an explicit UNKNOWN at a declared resource bound instead of looping forever or faking a NO.
Theorem-Prover-Guided Search — Uses an automated or interactive prover to search for and mechanically check the proof or certificate a boundary claim rests on, recording the verified guarantee and any open residue.
Turing-Reduction Analysis — Asks whether a problem becomes solvable given an oracle for another, placing it among the degrees of relative computability rather than in a flat decidable/undecidable split.

Compression statement¶

Fix the problem, representation, computation model, quantifiers, and guarantee; seek either a constructive total procedure or a sound impossibility transfer; classify the result as decidable/computable, one-sided recognizable, partial or relative, undecidable/uncomputable, or unresolved; then restrict the domain, weaken the output contract, add bounded approximation or interaction, expose unknown, or decline the task without confusing nontermination, complexity, and impossibility.

Canonical formula: B(P, R, M, G) → (status, evidence, decidable_subclasses, fallback), where P is the problem class, R the representation, M the computation model, and G the required guarantee.

Abstractions this archetype builds on — directly (a source ingredient) or as a related pattern. Links follow the typed catalog namespace.

Built directly on (3)

Algorithm: Step-by-step problem-solving procedure.
Computability: The in-principle boundary between problems an effective procedure can solve and those none can.
Decidability Computability: A class of yes/no questions admits a finite procedure that always terminates with the correct answer.

Also references 22 related abstractions

Abstraction: Focus on core elements.
Applicability Scope: An artifact publishes a bounded region of conditions under which its outputs or guarantees hold, so consumers can detect out-of-scope use before it causes harm.
Approximation: Good-enough representation.
Axiomatic Incompatibility: A small set of individually plausible axioms is provably jointly unsatisfiable, forcing a chosen trade-off.
Boundedness: Values remain within limits.
Complexity (Time/Space): Resource scaling with input size.
Constraint: Limits possibilities to guide outcomes.
Diagonal Impossibility: In a self-modeling system, a putative total analyzer is refuted by constructing an object engineered to make the analyzer's verdict on it contradict the property it decides.
Embeddability: Whether a structured substrate admits a conflict-free placement inside a constrained ambient target.
Formal System: Symbols, formation rules, axioms, and inference rules closed under mechanical derivation.

▸ Show 12 more

Variants¶

Narrower or domain-specific specializations that share this archetype's core structure. Recognized variants are established; candidate variants are provisional.

Decision-Problem Decidability Mapping · subtype · recognized

Classifies whether a yes/no problem has a correct procedure that terminates on every valid input, with recognizability and complement behavior recorded when total decision fails.

Distinct from parent: The parent also covers function computation, enumeration, synthesis, and other effective mappings; this variant specializes the status lattice to yes/no problems.
Use when: The required output is a Boolean membership, validity, safety, or property judgment; A universal termination guarantee matters rather than eventual success on selected instances; Positive and negative cases may have asymmetric certificates or search behavior.
Typical domains: program analysis, formal logic, database query languages, model checking
Common mechanisms: constructive algorithm and correctness proof, many one reduction proof, semi decision with explicit unknown

Semi-Decision and Recognizability Mode · risk or failure variant · recognized

Uses a one-sided terminating recognizer while preserving an explicit unknown or still-searching state for the side that lacks a guaranteed halt.

Distinct from parent: The parent classifies all statuses; this variant operationalizes the recognizable-but-not-decidable region.
Use when: Positive instances have checkable finite witnesses or enumerable derivations; No total decision procedure is known or possible for the full class; The operational context can tolerate abstention, waiting, bounded timeout, or escalation without converting silence into falsehood.
Typical domains: theorem proving, program synthesis, symbolic search, compliance evidence
Common mechanisms: enumeration and dovetailing, semi decision with explicit unknown, fallback mode router

Restricted-Domain Computability Recovery · subtype · recognized

Recovers total solvability by narrowing the language, state space, input promise, recursion depth, numeric representation, or instance size to a decidable fragment.

Distinct from parent: The parent maps the boundary; this variant chooses a specific scope-restriction response that crosses from an undecidable region into a decidable one.
Use when: The unrestricted class is undecidable or its status is too uncertain for deployment; A useful subset can be recognized before invoking the solver; The lost expressiveness or coverage can be stated and accepted.
Typical domains: static analysis, query languages, rule engines, finite state verification
Common mechanisms: bounded domain exhaustive search, promise problem restriction, language fragment restriction, abstract interpretation or model checking

Relative or Interactive Computability Analysis · implementation variant · recognized

Reclassifies solvability relative to declared oracle access, interaction, human input, external measurement, or trusted advice rather than silently treating those capabilities as free computation.

Distinct from parent: The parent can use an ordinary closed computation model; this variant centers relative capability and interaction assumptions.
Use when: A proposed solution depends on questions answered by another service, expert, sensor, database, or proof source; The external capability may itself be partial, delayed, fallible, unavailable, or non-effective; The distinction between autonomous and assisted solvability matters.
Typical domains: human in the loop systems, oracle assisted reasoning, sensor driven control, proof carrying services
Common mechanisms: turing reduction analysis, fallback mode router, computability boundary decision record

Near names: Computability Assessment, Algorithmic Solvability Analysis, Decidability Analysis, Church–Turing Thesis, Halting-Problem Analysis, Effective-Procedure Boundary Review.