Rice’s Theorem

Expanded Definition

Rice's Theorem is a result from computability theory that applies to programs as semantic objects, meaning it concerns what a program computes or whether it has a behavioural property rather than how the code is structured. For security teams, that distinction matters because many desirable questions are semantic: whether software is malicious, whether an agent will leak a secret, whether a transformation preserves policy, or whether a model-driven tool will always behave safely. The theorem says that if a property is both non-trivial and about program meaning, then no universal algorithm can decide it for every possible program.

That does not mean useful analysis is impossible. It means analysis must be bounded, approximated, or scoped to restricted classes of software. In practice, teams lean on static analysis, dynamic testing, sandboxing, policy checks, and formal methods where the problem space is narrow enough to make progress. The idea is closely aligned with the practical limits reflected in the NIST Cybersecurity Framework 2.0, which treats risk management as a disciplined process rather than a promise of perfect detection. The most common misapplication is assuming a scanner, theorem prover, or AI system can conclusively determine every dangerous behaviour in arbitrary code, which occurs when teams ignore undecidability and demand universal answers from general-purpose analysis.

Examples and Use Cases

Applying Rice's Theorem rigorously often introduces a completeness tradeoff, requiring organisations to weigh stronger assurance against the fact that exhaustive verdicts are not always computable.

• Malware detection teams can often identify known patterns or suspicious behaviour, but they cannot build a single perfect algorithm that decides whether any arbitrary program is malicious in all cases.
• Code review tools can flag use of secrets, network calls, or unsafe deserialisation, yet they cannot universally determine whether a program will eventually reach a harmful state for every input.
• Agentic AI security checks may look for unsafe tool use or prompt injection exposure, but they cannot generally prove that an autonomous agent will never take a risky action in every possible execution path.
• Policy engines can verify narrow constraints, such as whether a deployment includes forbidden permissions, but they cannot decide every semantic question about how the software will behave at runtime.
• Program analysis in research settings often relies on restricted languages, bounded execution, or model-specific assumptions because unrestricted software quickly runs into the limits described by formal computability theory.

For teams building controls around software and AI workflows, the lesson is that assurance comes from narrowing the question, not from expecting universal decision procedures. That is why standards-oriented governance such as the NIST Cybersecurity Framework 2.0 emphasises layered safeguards, monitoring, and response rather than absolute certainty.

Why It Matters for Security Teams

Rice's Theorem explains a hard limit behind many security and assurance failures: if a team asks a tool to answer a semantic question about arbitrary software, the tool will eventually face cases it cannot decide. That limit shows up in vulnerability triage, malicious code classification, policy enforcement, and automated review of AI-enabled systems. It is especially relevant where NHI, secrets, or agentic AI are involved, because the real security question is often whether a program will eventually access a token, invoke a tool, or cross a trust boundary in a harmful way.

Security teams should treat this as a design constraint. Instead of pursuing perfect universal analysis, they should define bounded environments, choose measurable properties, and combine controls such as sandboxing, least privilege, observability, and manual review. In standards terms, the NIST Cybersecurity Framework 2.0 is useful because it frames risk as something to be managed continuously, not eliminated through a single check. Organisations typically encounter the practical consequences only after an automation pipeline or security gate fails to give a definitive answer on an edge case, at which point Rice's Theorem becomes operationally unavoidable to address.