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.
Wikipedia contributors, "Rice–Shapiro theorem", Wikipedia, revision 1381342572, retrieved 20 November 2026, source, CC BY-SA 4.0.