Every nontrivial semantic property of the behavior of computer programs, meaning any property that depends only on which function a program computes rather than on its code, is undecidable. Proved by Henry Gordon Rice, it is a sweeping generalization of the undecidability of the halting problem.
Facts
StatementEvery non-trivial semantic property of the partial function computed by a program, meaning any property that depends only on program behavior and is neither true of every program nor false of every program, is undecidable. 1 Classification
Statement Form Connections
Has Statement Form
In Branch
Sources
1. Rice's theorem (Wikipedia)
Wikimedia FoundationLead section, first sentence
In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable.
Introduction section, attribution sentence
The theorem is named after Henry Gordon Rice, who proved it in his doctoral dissertation of 1951 at Syracuse University.
In Group: Computability and Complexity Theory, Lead section
In computability theory, Rice's theorem states that all non-trivial semantic
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.