{"schema_version":1,"experiment_id":"eoa_inverse_innovation_exp09_archetype_breadth150_20260804","cell_id":"computability_boundary_mapping__computer_science","arm":"BREADTH_PROBE_ONE_SHOT","candidate_id":"computability_boundary_mapping__computer_science__P1","proposal_index":1,"version":0,"title":"Truthful Safety Contracts for Automated Package-Upgrade Approval","problem":"A software platform team wants an auto-merge service that accepts an existing package, a proposed replacement, and an arbitrary client program, then always terminates with a Boolean answer to whether the replacement preserves all client-observable behavior for every possible input. The service treats this unrestricted semantic-equivalence question as an ordinary analyzer implementation problem, despite allowing Turing-complete package and client code.","actors":["Platform team specifying the upgrade service","Analyzer engineers","Repository owners reviewing dependency updates","Security engineers seeking prompt patch adoption","Developers whose applications consume upgraded packages","Independent reviewer of computability arguments"],"observable_state":"The upgrade queue contains arbitrary-code updates for which testing, symbolic execution, or comparison reaches a resource limit; the current interface nevertheless requires SAFE or UNSAFE. Timeouts are consequently converted into rejection, manual guesswork, or an unsupported safety label, while successful test runs are liable to be interpreted as universal equivalence evidence.","consequence":"The platform can misstate what its analyzer established, block useful upgrades because search was inconclusive, approve an update beyond the evidence, or continue investing in a total exact analyzer whose unrestricted guarantee may be impossible. Repository owners cannot distinguish a discovered behavioral difference from incomplete analysis.","affected_objective":"Provide dependable, reviewable package-upgrade decisions without confusing bounded evidence, nontermination, and class-wide semantic equivalence, while preserving an operational route for updates outside an exactly decidable fragment.","intervention":"Replace the mandatory unrestricted SAFE/UNSAFE oracle with a computability-boundary decision record and a routed guarantee contract. Precisely define client-observable equivalence, finite encodings, the computation model, and the universal quantifiers. Attempt a halting-problem many-one reduction by constructing, from a program M and input w, an old package operation that diverges and a proposed operation that simulates M(w), returning only if M halts; a total equivalence decider would distinguish halting from nonhalting. Subject that argument and its observation model to independent proof checking before changing requirements. If validated, reserve total SAFE/UNSAFE decisions for an enforceable finite-state package fragment, use counterexample search to return VERIFIED_DIFFERENCE outside it, and otherwise return TESTED_WITHIN_BOUND, UNKNOWN, or OUT_OF_SCOPE. A fallback-mode router sends those states to repository-owner review rather than converting them into Boolean conclusions.","structural_mapping":[{"archetype_element":"Problem-Class Specification","domain_realization":"The decision problem is whether old and proposed package versions are observationally equivalent for every input and every client admitted by the declared interface, rather than whether one sampled test suite passes."},{"archetype_element":"Instance Representation Contract","domain_realization":"An instance is a finite encoding of two package versions, their exported interface, a client-language definition, and an observation policy covering returned values, exceptions, output, state changes, and termination."},{"archetype_element":"Computation Model Contract","domain_realization":"The unrestricted class permits ordinary Turing-complete programs but no human oracle, hidden execution bound, or semantic-equivalence service; the restricted path permits only statically validated finite-state programs."},{"archetype_element":"Solvability Guarantee Profile","domain_realization":"The requested unrestricted guarantee is sound, complete, exact, uniform, and terminating; fallback labels explicitly relinquish completeness or unrestricted scope."},{"archetype_element":"Quantifier and Scope Map","domain_realization":"The record separates one update, tested inputs, all inputs to a finite-state fragment, and all clients and inputs in the unrestricted language."},{"archetype_element":"Computability Impossibility Certificate","domain_realization":"A reviewed reduction maps each encoded M,w pair to an upgrade-equivalence instance whose behavioral difference reveals whether M halts."},{"archetype_element":"Decidable Subclass Map","domain_realization":"The candidate exact fragment excludes unbounded loops, recursion, dynamic code loading, unbounded allocation, and external nondeterministic calls, and bounds data domains so state exploration terminates."},{"archetype_element":"Unknown and Nontermination Policy","domain_realization":"Resource exhaustion, cancelled analysis, incomplete exploration, and unsupported language features remain distinct from VERIFIED_DIFFERENCE and from fragment-level SAFE."},{"archetype_element":"Fallback Solution Contract","domain_realization":"Outside the decidable fragment, the service may provide a concrete counterexample, bounded test evidence, UNKNOWN, or OUT_OF_SCOPE and then route the merge decision to an authorized owner."},{"archetype_element":"Recheck Trigger","domain_realization":"Adding recursion, unbounded data, concurrency, external calls, a new observation type, or a stronger public guarantee reopens the classification."},{"archetype_element":"Complexity Follow-On Gate","domain_realization":"Only after totality is established for the finite-state fragment does the team assess whether exhaustive comparison meets practical time and memory limits."}],"mechanism_mapping":[{"mechanism_slug":"halting_problem_reduction","role":"Tests whether a universal terminating semantic-equivalence oracle would decide program halting under the same program and observation model.","counterfactual_removal":"Without the reduction, the team would have only analyzer failures and timeouts, which cannot justify an impossibility classification."},{"mechanism_slug":"reduction_direction_checklist","role":"Checks that halting instances are computably translated into upgrade instances and that equivalence outcomes preserve the intended halting distinction.","counterfactual_removal":"A reversed or observation-breaking translation could produce an invalid impossibility claim and prematurely narrow the product."},{"mechanism_slug":"language_fragment_restriction","role":"Creates an enforceable finite-state package subset in which exhaustive equivalence checking has a termination argument.","counterfactual_removal":"The service would have no exact operational region and might either abandon useful automation or quietly retain the unrestricted claim."},{"mechanism_slug":"semi_decision_with_explicit_unknown","role":"Allows counterexample search to confirm a behavioral difference while preserving UNKNOWN when no difference has been established within the budget.","counterfactual_removal":"Timeouts would again be pressured into SAFE or UNSAFE, recreating the original epistemic error."},{"mechanism_slug":"fallback_mode_router","role":"Routes fragment members to the total checker and all other updates to counterexample search, bounded evidence, owner review, or abstention.","counterfactual_removal":"Correct labels would exist on paper but would not reliably control operational merge decisions."},{"mechanism_slug":"proof_checking","role":"Assigns an independent reviewer to validate the reduction, representation assumptions, and permitted public wording.","counterfactual_removal":"The same team benefiting from a changed requirement could accept a theorem-assumption mismatch without effective challenge."}],"causal_chain":["An unrestricted Turing-complete upgrade-equivalence requirement demands an exact terminating answer across all admitted programs and inputs.","The Boolean interface hides the distinction between a proved difference, bounded non-discovery, timeout, and unsupported input.","Engineering searches are therefore interpreted as decisions even though their completion behavior does not establish the universal guarantee.","A precise problem, representation, model, quantifier, and observation contract makes the claimed mapping suitable for constructive or impossibility analysis.","A checked halting-problem reduction, if valid, rules out the requested total exact decider under that contract rather than merely documenting poor performance.","An enforceable finite-state restriction moves a declared subset to a class where exhaustive comparison terminates.","Explicit evidence states and the fallback router prevent results outside that subset from inheriting the fragment's exact guarantee.","Repository owners receive differentiated evidence and retain authority over unresolved updates, while language or guarantee changes trigger reclassification."],"baseline":"Continue using tests, bounded execution, symbolic analysis, and timeouts behind a mandatory SAFE/UNSAFE result, with no versioned statement of the program class, observation semantics, totality claim, or meaning of resource exhaustion.","nearest_rivals":["Property-based or differential testing, which can expose behavioral differences on generated executions but does not by itself establish equivalence for every execution.","Bounded model checking, which can decide behavior inside a stated state or execution bound but cannot silently transfer that guarantee to arbitrary unbounded programs.","Conservative static analysis, which may be sound for a selected property while returning false positives or unknown and therefore does not supply the requested exact complete decider.","Manual repository-owner review, which can make a release decision using contextual judgment but is not a uniform effective procedure proving semantic equivalence.","A blanket ban on automated approval for all code, which avoids overclaiming but discards the decidable finite-state region and differentiated evidence."],"remaining_contrastive_claim":"The candidate's distinguishing contribution is not another upgrade predictor or test generator. It first adjudicates whether the requested universal, exact, terminating equivalence guarantee is supportable under a fixed formal contract; it then uses that classification to partition inputs and output meanings so that exact fragment decisions, witnessed differences, bounded evidence, and unresolved cases cannot be presented as interchangeable.","authority_safety":{"decision_authority":"Repository owners retain merge authority, the security owner retains emergency-patch authority, and the designated formal-methods reviewer approves only the computability classification and permitted guarantee language. The pilot analyzer may label evidence but may not merge, reject, or roll back code.","authorized_first_step":"Conduct an offline proof-and-interface exercise on twelve synthetic package pairs: four finite-state equivalent pairs, four finite-state nonequivalent pairs with known witnesses, and four unrestricted pairs derived from small halting-reduction fixtures. Record routing and output labels without affecting any repository.","excluded_actions":["Automatically merging or rejecting dependency updates","Relabeling historical production decisions","Claiming the reduction is valid before independent review","Advertising unrestricted upgrades as safe based on fragment-level results","Treating UNKNOWN, timeout, cancellation, or OUT_OF_SCOPE as SAFE or UNSAFE","Expanding the supported language during the pilot"],"halt_rollback":"Stop the exercise if the observation semantics cannot be made unambiguous, the fragment-membership check admits unsupported constructs, a fixture receives a stronger label than its evidence permits, or the reviewer finds a reduction-direction or model mismatch. Discard pilot labels and restore the unchanged existing workflow; no production decision is modified."},"negative_tests":{"strongest_counterevidence":"A uniform effective procedure accompanied by a valid proof of correctness and termination for the exact unrestricted package, client, observation, and computation contracts would defeat the proposed impossibility classification and remove the rationale for boundary-based routing.","problem_falsifier":"The problem is absent if stakeholders only require bounded empirical regression evidence for named updates and do not require or communicate universal semantic equivalence, totality, or a Boolean interpretation of timeout.","intervention_falsifier":"The intervention fails if independently reviewed labels still cause repository owners or downstream automation to treat TESTED_WITHIN_BOUND, UNKNOWN, or OUT_OF_SCOPE as equivalent to proved safety, or if the declared finite-state boundary cannot be conservatively enforced before analysis.","risks":["The formal observation contract may omit behavior developers consider material, making a correct theorem semantically irrelevant.","The finite-state fragment may exclude too many real packages to justify its maintenance cost.","Users may reconstruct unbounded behavior through foreign functions, reflection, concurrency, or external services.","A flawed reduction or theorem-assumption mismatch could be used to terminate feasible engineering work.","UNKNOWN routing may concentrate manual review workload or delay urgent security updates.","A finite-state problem may be decidable yet too expensive for operational use, requiring a separate complexity assessment.","Evidence labels may be simplified by dashboards or APIs until their distinctions disappear.","The impossibility result could be misused to avoid improving bounded testing and counterexample discovery outside the exact fragment."]},"next_evidence_step":"Run the twelve-fixture offline exercise and have one independent reviewer check the finite encoding, observation semantics, translator computability, reduction direction, property preservation, fragment-membership enforcement, and every emitted label. The step ends with a pass/fail matrix and an unresolved-assumption list; it does not authorize production integration or any general effectiveness claim.","prior_art_status":"UNSEARCHED","diversity_from_prior_proposals":"No prior proposals or experiment artifacts were inspected under runtime isolation. This candidate is independently characterized by its package-upgrade semantic-equivalence problem, halting-reduction test, enforceable finite-state exact fragment, and non-Boolean evidence router; no comparative diversity claim is made.","revision_record":{"parent_version":null,"progress_targets_addressed":["Initial one-shot construction from the supplied archetype and computer-science domain card","Concrete problem, actors, observable state, consequence, and affected objective specified","Archetype structure and named mechanisms mapped to operational elements","Authority limits, safeguards, falsifiers, risks, and bounded evidence step included"],"conceptual_changes":["Initial version; no revision from an earlier candidate"],"operational_changes":["Initial version defines an offline twelve-fixture exercise with no production authority"],"evidence_changes":["Prior art remains unsearched; proposed evidence is limited to proof checking and synthetic offline routing tests"],"claim_changes":["No novelty, prevalence, demand, or effect-size claim is made"]}}