 Rice’s Theorem (3.4)  provides a means of showing that many decision problems of practical import are undecidable—e.g., of determining whether a program always returns an output or whether it correctly computes a given function (e.g., addition or multiplication). Its proof also shows that if \(I\) is a non-trivial index set, the problem of deciding \(x \in K\) can be “reduced” to that of deciding \(x \in I\) it the following sense: if we could effectively decide the latter, then we could also effectively decide the former by first calculating \(s^2_1(c,x)\) and then checking if this value is in \(I\). This method of showing undecidability will be formalized by the notion of a many-one reduction described in  Section 3.5  below.