Rice–Shapiro theorem

In computability theory, the Rice–Shapiro theorem is a generalization of Rice's theorem, and is named after Henry Gordon Rice and Norman Shapiro. In words, this helps in proving a set is not recursively enumerable and the only properties of the behavior of programs which can be semi-decidable are the “finitary properties” (properties which depend on the behaviour on a finite number/amount of inputs). The key idea it gives away is to leverage the existence of finite subfunctions to show undecidability. In particular, any statement made about computable function can be proven testing the values at finitely many arguments, stating there is no general algorithm that can decide whether an arbitrary program (or function) has a specific interesting property unless that property is true for all programs or false for none.

Formal statement

Let A be a set of partial-recursive unary functions on the domain of natural numbers such that the set [math]\displaystyle{ Ix(A):=\{ n \mid \varphi_n \in A \} }[/math] is recursively enumerable, where [math]\displaystyle{ \varphi_n }[/math] denotes the [math]\displaystyle{ n }[/math]-th partial-recursive function in a Gödel numbering.

Then for any unary partial-recursive function [math]\displaystyle{ \psi }[/math], we have:

[math]\displaystyle{ \psi \in A \Leftrightarrow \exists }[/math] a finite function [math]\displaystyle{ \theta \subseteq \psi }[/math] such that [math]\displaystyle{ \theta \in A. }[/math]

In the given statement, a finite function is a function with a finite domain [math]\displaystyle{ x_1,x_2,...,x_m }[/math] and [math]\displaystyle{ \theta \subseteq \psi }[/math] means that for every [math]\displaystyle{ x \in \{x_1,x_2,...,x_m\} }[/math] it holds that [math]\displaystyle{ \psi(x) }[/math] is defined and equal to [math]\displaystyle{ \theta(x) }[/math].

Perspective from effective topology

For any finite unary function [math]\displaystyle{ \theta }[/math] on integers, let [math]\displaystyle{ C(\theta) }[/math] denote the 'frustum' of all partial-recursive functions that are defined, and agree with [math]\displaystyle{ \theta }[/math], on [math]\displaystyle{ \theta }[/math]'s domain.

Equip the set of all partial-recursive functions with the topology generated by these frusta as base. Note that for every frustum [math]\displaystyle{ C }[/math], [math]\displaystyle{ Ix(C) }[/math] is recursively enumerable. More generally it holds for every set [math]\displaystyle{ A }[/math] of partial-recursive functions:

[math]\displaystyle{ Ix(A) }[/math] is recursively enumerable iff [math]\displaystyle{ A }[/math] is a recursively enumerable union of frusta.

References

• Cutland, Nigel (1980). Computability: an introduction to recursive function theory. Cambridge University Press. ; Theorem 7-2.16.
• Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT Press. pp. 482. ISBN 0-262-68052-1. 
• Odifreddi, Piergiorgio (1989). Classical Recursion Theory. North Holland.