Editing Rice's theorem (section)

==Introduction==
Rice's theorem puts a theoretical bound on which types of [[static program analysis|static analysis]] can be performed automatically. One can distinguish between the [[syntax (programming languages)|syntax]] of a program, and its [[semantics (computer science)|semantics]]. The syntax is the detail of how the program is written, or its "intension", and the semantics is how the program behaves when run, or its "extension". Rice's theorem asserts that it is impossible to decide a property of programs which depends only on the semantics and not on the syntax, unless the property is trivial (true of all programs, or false of all programs).

By Rice's theorem, it is impossible to write a program that automatically verifies for the absence of [[software bug|bugs]] in other programs, taking a program and a [[formal specification|specification]] as input, and checking whether the program satisfies the specification.

This does not imply an impossibility to prevent ''certain types'' of bugs. For example, Rice's theorem implies that in [[dynamic programming language|dynamically typed programming languages]] which are [[Turing completeness|Turing-complete]], it is impossible to verify the absence of type errors. On the other hand, [[static typing|statically typed programming languages]] feature a type system which statically prevents type errors. In essence, this should be understood as a feature of the ''syntax'' (taken in a broad sense) of those languages. In order to type check a program, its source code must be inspected; the operation does not depend merely on the hypothetical semantics of the program.

In terms of general software verification, this means that although one cannot algorithmically check whether any given program satisfies a given specification, one can require programs to be annotated with extra information that proves the program is correct, or to be written in a particular restricted form that makes the verification possible, and only accept programs which are verified in this way. In the case of type safety, the former corresponds to type annotations, and the latter corresponds to [[type inference]]. Taken beyond type safety, this idea leads to correctness proofs of programs through proof annotations such as in [[Hoare logic]].

Another way of working around Rice's theorem is to search for methods which catch ''many'' bugs, without being complete. This is the theory of [[abstract interpretation]].

Yet another direction for verification is [[model checking]], which can only apply to finite-state programs, not to Turing-complete languages.