The Rice-Shapiro Theorem, developed by Henry Gordon Rice and Norman Shapiro, generalizes Rice's Theorem from decidable to semi-decidable properties of partial computable functions. It states that a semi-decidable property can hold of a partial computable function only if it already holds of some finite piece of that function, reflecting the fact that a program can only be tested by running it on finitely many inputs. It sits alongside the related Kreisel-Lacombe-Shoenfield-Tseitin theorem, proved independently by several logicians around 1959, which reaches a similar conclusion for decidable properties of total computable functions.
Facts
StatementIf P is a set of partial computable functions whose index set, the set of program indices e such that the function computed by program e belongs to P, is semi-decidable, then a partial computable function f belongs to P if and only if P already contains some finite subfunction of f, that is, a partial function defined at only finitely many points that agrees with f on those points. 1 Sources
1. Rice-Shapiro theorem, Wikipedia
Formal statement sectionQuote, Formal statement section
Let P be a set of partial computable functions such that the index set of P (i.e., the set of indices e such that φ_e∈P, for some fixed admissible numbering φ) is semi-decidable. Then for any partial computable function f, it holds that P contains f if and only if P contains a finite subfunction of f (i.e., a partial function defined in finitely many points, which takes the same values as f on those points).
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.