= Solution
Fix an effective enumeration $f_{e,n}$ of the $n$-ary <partial recursive function>[partial recursive functions].
The <S-m-n theorem> says that program inputs can be compiled into an index: for every $m,n\geq1$ there is a total recursive $s_n^m$ such that
$$
f_{s_n^m(e,x_1,\ldots,x_m),n}(y_1,\ldots,y_n)
\simeq f_{e,m+n}(x_1,\ldots,x_m,y_1,\ldots,y_n).
$$
Here $\simeq$ means that either both sides are undefined or both are defined and equal.
The <recursion theorem> says that every total recursive transformation $h$ of program indices has a semantic fixed point: some $e$ satisfies
$$
f_{e,1}\simeq f_{h(e),1}.
$$
The <Rice theorem> says that every nontrivial <extensional property of programs> computed by partial recursive functions is undecidable.
Back to article page
