{"schema_version":1,"experiment_id":"eoa_inverse_innovation_exp11_mechanism_context_external20_20260804","research_id":"eoa_inverse_innovation_exp11_external_scrutiny_20260804","cell_id":"computability_boundary_mapping__engineering_design","opaque_id":"computability_boundary_mapping__engineering_design__C","search_lanes":{"direct_problem":{"queries":["universal controller safety verification undecidable programmable controllers control systems","Blondel Tsitsiklis survey computational complexity undecidability systems control pdf","hybrid systems safety verification undecidable decidable subclasses primary paper"],"source_ids":["SRC1","SRC2"],"no_result_note":null},"closest_prior_art":{"queries":["formal verification controller safety unknown timeout certification guidance","FAA DO-333 formal methods assumptions verification certification PDF","formal verification tools three valued result true false unknown model checking industrial"],"source_ids":["SRC1","SRC3","SRC4","SRC5","SRC6","SRC8"],"no_result_note":null},"historical_terminology":{"queries":["algorithmic unsolvability absolute stability control systems old terminology undecidable","What's Decidable about Hybrid Automata full text 1998","algorithmic problem unsolvable stability control systems"],"source_ids":["SRC1","SRC2"],"no_result_note":null},"products_practices_standards":{"queries":["CBMC official documentation bounded model checking unwinding assertions completeness threshold","UPPAAL official documentation symbolic model checking finite state timed automata limitations","IEC 61508 formal methods assumptions verification independent assessment official","Prover PSL model checker CENELEC EN 50128 SIL 4"],"source_ids":["SRC3","SRC4","SRC5","SRC6","SRC8"],"no_result_note":null},"non_english_regional":{"queries":["Unentscheidbarkeit Sicherheitsverifikation Steuerungssysteme Regelungssysteme Modellprüfung","vérification sécurité systèmes hybrides indécidable sous-classes décidables","verificación seguridad controladores sistemas híbridos indecidible alcance modelo","UML-basierte Modellierung und Verifikation von Steuerungen"],"source_ids":["SRC7","SRC8"],"no_result_note":null},"composition_subproblems":{"queries":["hybrid systems reachability undecidable finite-state bounded decidable subclass","bounded model checking counterexample completeness finite bound controller verification","formal verification assumptions abstraction independent proof checker certification","simulation assertion based verification model checking controller plant model"],"source_ids":["SRC1","SRC2","SRC4","SRC5","SRC6","SRC7","SRC8"],"no_result_note":null}},"sources":[{"source_id":"SRC1","title":"What's decidable about hybrid automata?","url":"https://research-explorer.ista.ac.at/record/4492","publisher":"Institute of Science and Technology Austria repository; Journal of Computer and System Sciences (Elsevier)","date_or_year":"1998","source_type":"PRIMARY_RESEARCH","language":"English","claims_supported":["Safety-relevant verification tasks for embedded control programs can be represented as hybrid-automaton reachability problems.","Reachability is decidable with a terminating PSPACE procedure for initialized rectangular automata.","Small extensions of that restricted class, including adding one stopwatch to timed automata, make reachability undecidable.","A formal boundary between terminating decidable subclasses and undecidable generalizations is established prior art."]},{"source_id":"SRC2","title":"A survey of computational complexity results in systems and control","url":"https://www.mit.edu/~jnt/Papers/J080-00-vb-survey.pdf","publisher":"Automatica (Elsevier); author copy hosted by Massachusetts Institute of Technology","date_or_year":"2000","source_type":"SECONDARY_RESEARCH","language":"English","claims_supported":["Undecidability and computational complexity are established concerns in systems and control, including stability, robust control, nonlinear systems, and hybrid systems.","Some bounded problems have direct finite procedures while their unbounded counterparts are mathematically unsolvable.","Undecidability, unresolved status, and computational intractability are distinct classifications and should not be conflated."]},{"source_id":"SRC3","title":"AC 20-115D — Airborne Software Development Assurance Using EUROCAE ED-12( ) and RTCA DO-178( )","url":"https://www.faa.gov/airports/resources/advisory_circulars/index.cfm/go/document.information/documentNumber/20-115D","publisher":"U.S. Federal Aviation Administration","date_or_year":"2017","source_type":"OFFICIAL_GUIDANCE","language":"English","claims_supported":["The FAA identifies a concrete certification authority and software applicants as users and authorizers of assurance evidence.","The FAA recognizes DO-333/ED-216 formal-methods guidance as an acceptable certification means when its applicable conditions are followed.","Formal verification is situated within an accountable certification process rather than functioning as automatic certification authority."]},{"source_id":"SRC4","title":"Software Assurance Approaches, Considerations, and Limitations (DOT/FAA/TC-15/57)","url":"https://www.faa.gov/sites/faa.gov/files/aircraft/air_cert/design_approvals/air_software/TC-15-57.pdf","publisher":"U.S. Federal Aviation Administration William J. Hughes Technical Center","date_or_year":"2016","source_type":"PRIMARY_RESEARCH","language":"English","claims_supported":["Airbus, Dassault Aviation, and Rockwell Collins provide identifiable industrial adopters of formal and model-based assurance practices.","Formal verification used for certification credit depends on explicit contracts and assumptions about the runtime environment and parameter ranges.","Abstractions and assumptions can make formal-verification results misleading or erroneous and therefore must be documented, validated, and justified.","Inspection, traceability, coverage objectives, and human review remain necessary around automated verification."]},{"source_id":"SRC5","title":"UPPAAL Documentation","url":"https://docs.uppaal.org/","publisher":"UPPAAL development team","date_or_year":"Accessed 2026-08-04","source_type":"FIRST_PARTY_PRODUCT","language":"English","claims_supported":["A deployed verification product explicitly limits its applicability to systems representable as communicating timed automata with finite control structure and real-valued clocks.","The tool supports modeling, simulation, and symbolic verification of real-time controllers within that declared representation.","This is existing practice for enforcing a restricted analyzable model class, but it is not a universal checker for arbitrary programmable controllers and physical environments."]},{"source_id":"SRC6","title":"CBMC: The C Bounded Model Checker","url":"https://arxiv.org/abs/2302.02384","publisher":"Springer chapter preprint by CBMC maintainers; arXiv","date_or_year":"2023","source_type":"PRIMARY_RESEARCH","language":"English","claims_supported":["CBMC finds assertion violations or proves safety only under a stated unwinding bound.","Bounded model checking is a semi-decision procedure; completeness requires a finite completeness threshold, and CBMC has limited support for unbounded verification.","An unsatisfiable bounded formula excludes violations only within the specified unwinding bounds.","The paper explicitly distinguishes useful bounded results from universal unbounded assurance."]},{"source_id":"SRC7","title":"UML-basierte Modellierung und Verifikation von Steuerungen","url":"https://publica.fraunhofer.de/entities/publication/331d811b-39dd-4eaf-90b1-c2cf98bba7c7","publisher":"Fraunhofer-Gesellschaft","date_or_year":"2009","source_type":"PRIMARY_RESEARCH","language":"German","claims_supported":["German engineering literature identifies safety-critical controller complexity as motivating combined simulation-based and formal verification.","The demonstrated workflow combines a joint controller/plant model, design-rule checking, assertion-based simulation, and model checking.","Plant reactions are discretized for model checking, illustrating that conclusions depend on an explicit abstraction of the physical plant.","The workflow produces counterexamples for failed properties but does not supply the proposal's full computability-status and governed-fallback record."]},{"source_id":"SRC8","title":"Prover PSL","url":"https://www.prover.com/products/prover-psl/","publisher":"Prover Technology AB","date_or_year":"2025","source_type":"FIRST_PARTY_PRODUCT","language":"English","claims_supported":["A commercial railway product combines bounded model checking, induction, interpolation, and IC3 for industrial formal verification.","Valid results can produce proof logs checkable by an independent checker, while falsified properties produce counterexamples.","The product is used in a CENELEC EN 50128 SIL 4 sign-off solution and has longstanding railway-control applications.","Existing industrial practice therefore covers bounded analysis, multiple proof strategies, independent proof checking, and safety sign-off, though not the complete proposed status lattice and escalation policy."]}],"problem_evidence":{"status":"PARTLY_SUPPORTED","finding":"The mathematical core exists: unrestricted or only slightly restricted hybrid-control reachability and several control-system properties are undecidable, while carefully restricted classes and bounded instances have terminating procedures. Products and assurance guidance also demonstrate scope-limited verification in real controller and certification settings. However, the retained public sources do not directly establish the proposal's stronger operational claim that engineering teams commonly demand one universal terminating checker or force timeout/unknown outcomes into safe/unsafe decisions.","source_ids":["SRC1","SRC2","SRC4","SRC5","SRC6","SRC7"],"uncertainty":"The impossibility result is model-relative and cannot be transferred to a deployed controller class without a faithful encoding and property-preserving proof. No internal requirements, incident reports, or empirical prevalence data were available for the alleged Boolean-coercion failure mode."},"adopter_evidence":{"status":"SUPPORTED","finding":"Identifiable adopters and authorizers exist: aircraft software applicants and FAA certification personnel operate under FAA-recognized formal-methods guidance; Airbus, Dassault Aviation, and Rockwell Collins have used formal verification or model-based assurance; railway infrastructure and signaling organizations use formal verification associated with SIL 4 sign-off. An accountable chief engineer, independent safety reviewer, or certification authority can authorize an offline classification pilot without delegating certification to the tool.","source_ids":["SRC3","SRC4","SRC7","SRC8"],"uncertainty":"The sources establish organizations and regulatory roles, but not that any named organization has requested this exact computability-boundary pilot or would adopt its five-way status vocabulary."},"implementation_evidence":{"status":"PARTLY_SUPPORTED","finding":"Most technical components are feasible and separately instantiated: formal decidability boundaries and constructive restricted algorithms; explicit assumptions and traceability; timed-automaton admission restrictions; bounded model checking; simulation plus model checking; counterexamples; and independently checkable proof logs. The exact integrated package—version-linked class specification, reviewed impossibility certificate, enforceable subclass map, distinct unknown/timeout/out-of-scope statuses, governed escalation, and recheck triggers—was not found as one routine engineering process, nor has its proposed four-week pilot effect been demonstrated.","source_ids":["SRC1","SRC3","SRC4","SRC5","SRC6","SRC7","SRC8"],"uncertainty":"A four-week, 20-design pilot appears technically bounded, but effort depends heavily on model availability, semantic fidelity, property formalization, and access to independent reviewers."},"prior_art":{"disposition":"ADJACENT_PRIOR_ART","closest_analogues":[{"name":"Decidability boundary for hybrid-automaton reachability","source_ids":["SRC1","SRC2"],"same_problem":true,"same_causal_lever":true,"overlap":"Prior research already formalizes embedded controller/plant behavior, proves undecidability for broad classes, supplies terminating algorithms for restricted subclasses, and distinguishes undecidable, unresolved, and merely complex cases.","remaining_difference":"It does not provide the proposal's organization-level, version-linked assurance record, machine-enforced admission contract, five-way operational result policy, accountable escalation path, or evidence that those governance additions improve certification decisions."},{"name":"DO-333-linked formal assurance with explicit assumptions and certification review","source_ids":["SRC3","SRC4"],"same_problem":true,"same_causal_lever":false,"overlap":"FAA-recognized practice already scopes formal claims through contracts, environment and parameter assumptions, traceability, inspections, coverage objectives, and certification authority.","remaining_difference":"The guidance and report do not require a computability proof for every admitted problem class or a unified decidable/recognizable/partial/unresolved map with separate timeout and out-of-scope outcomes."},{"name":"Restricted and bounded verification tools: UPPAAL and CBMC","source_ids":["SRC5","SRC6"],"same_problem":true,"same_causal_lever":true,"overlap":"These tools operationalize finite-control or bounded analysis, expose modeling assumptions and bounds, find counterexamples, and delimit when a safety conclusion is complete.","remaining_difference":"They are analyzers rather than an end-to-end assurance-governance system; neither source establishes the proposed cross-tool decision record, fallback escalation, recheck triggers, or reviewed impossibility certificate."},{"name":"Industrial controller verification and independently checkable sign-off evidence","source_ids":["SRC7","SRC8"],"same_problem":true,"same_causal_lever":false,"overlap":"Applied controller workflows already combine plant/controller modeling, simulation, assertions, model checking, bounded proof strategies, counterexamples, independent proof checking, and safety sign-off.","remaining_difference":"The public descriptions do not show an explicit computability-boundary investigation preceding automation or a governed policy that keeps unknown, timeout, and out-of-scope distinct from safe and unsafe."}],"contrastive_claim_remaining":"For assurance programs that currently combine simulation, bounded checking, and formal review, adding a version-linked computability-boundary record with enforceable admission constraints and distinct safe, unsafe, unknown, timeout, and out-of-scope statuses will produce reproducible corrections to claim scope or fallback decisions, without material decision delay, beyond what existing scoped tools and certification practices already achieve.","contrastive_claim_falsifier":"The incremental claim is falsified if independent reviewers cannot reproduce the classifications, if the pilot produces no corrections to scope/status/fallback relative to existing records, or if equivalent computability classification and five-way fallback governance is already routinely required and used in the sampled assurance process.","confidence":"MODERATE","search_limitations":"The search used exactly eight retained direct sources across six adversarial lanes. It included primary research, FAA guidance and research, first-party product documentation, older terminology, German-language engineering literature, and component combinations. Full paywalled standards such as DO-333, IEC 61508, and EN 50128 were not independently inspected; public FAA recognition and first-party product claims were used instead. The search did not inspect private assurance records, procurement requirements, incident databases, patents, or non-indexed regional literature."},"researchability_gates":{"externally_supported_problem":{"status":"PASS","rationale":"Primary and secondary research directly establish model-relative undecidability for broad controller-relevant hybrid classes and terminating verification for restricted classes; tools demonstrate that boundedness and representation scope matter operationally. The prevalence of Boolean coercion remains unproven but does not negate the externally supported boundary problem.","source_ids":["SRC1","SRC2","SRC5","SRC6"]},"identifiable_adopter_or_authorizer":{"status":"PASS","rationale":"FAA certification stakeholders, aircraft manufacturers, railway infrastructure organizations, verification engineers, and independent checkers are identifiable users or authorizers of formal assurance evidence.","source_ids":["SRC3","SRC4","SRC7","SRC8"]},"distinct_testable_incremental_claim":{"status":"PASS","rationale":"Despite very close theoretical and tool prior art, a credible incremental claim remains about whether an integrated, version-linked boundary/status/fallback record changes real assurance decisions beyond existing scoped verification and certification processes. That claim is observable and falsifiable in archived cases.","source_ids":["SRC3","SRC4","SRC5","SRC6","SRC8"]},"bounded_next_evidence_step":{"status":"PASS","rationale":"An offline pilot on 20 archived designs can compare existing conclusions against independently reproduced class, scope, bound, and result-status classifications without altering certification or deployment. Existing industrial case evidence makes this technically plausible.","source_ids":["SRC4","SRC7","SRC8"]},"no_unresolved_safety_or_authority_stop":{"status":"PASS","rationale":"The proposed first step is offline, preserves existing certification controls, prohibits converting unknown or timeout to safe, and includes halt conditions for unsafe misclassification or semantically incomplete models. FAA evidence confirms that formal evidence remains embedded in accountable certification rather than replacing authority.","source_ids":["SRC3","SRC4"]},"adequate_search_evidence":{"status":"PASS","rationale":"All six lanes were searched adversarially. The eight retained sources represent seven publisher or institutional groups and include three primary-research sources, two official FAA sources, and two first-party verification-product sources, plus German-language applied research.","source_ids":["SRC1","SRC2","SRC3","SRC4","SRC5","SRC6","SRC7","SRC8"]}},"strict_success":true,"screen_survival":true,"remaining_research_value":"MODERATE","recommended_next_step":"Pre-register and run the four-week offline pilot on 20 archived controller-assurance designs. For each, have two independent reviewers record the controller, plant, and environment semantics; quantifiers; bounds; soundness, completeness, and termination claims; admission status; and one of safe, unsafe, unknown, timeout, or out-of-scope. Compare with the original assurance record using predefined outcomes: number of corrected scope/status/fallback decisions, inter-reviewer agreement, reproducibility, elapsed review time, and any safety-relevant model omissions. Preserve all existing certifications and halt under the stated safety conditions.","world_novelty_boundary":"The bounded search establishes neither world novelty nor absence of additional prior art. It found a very close pre-existing theoretical mechanism—mapping decidability boundaries and constructing restricted terminating procedures—and mature adjacent assurance and product practices. The potentially researchable remainder is the measured effect of integrating those elements into a governed, version-linked engineering decision workflow. No conclusion is made about patentability, freedom to operate, market size, adoption probability, realized safety impact, or global superiority."}