Rice–Shapiro theorem

In computability theory, the Rice–Shapiro theorem is a generalization of Rice's theorem, named after Henry Gordon Rice and Norman Shapiro. It states that when a semi-decidable property of partial computable functions is true on a certain partial function, one can extract a finite subfunction such that the property is still true.

The informal idea of the theorem is that the "only general way" to obtain information on the behavior of a program is to run the program, and because a computation is finite, one can only try the program on a finite number of inputs.

A closely related theorem is the Kreisel-Lacombe-Shoenfield-Tseitin theorem (or KLST theorem), which was obtained independently by Georg Kreisel, Daniel Lacombe and Joseph R. Shoenfield , and by Grigori Tseitin.