On recognizing invariant properties of algorithms

N. K. Kossovski

Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part V, Tome 32 (1972), pp. 29-34

Résumé

Let $R$ be an enumerable class of partial recursive functions with a partial recursive universal function $u$ satisfying some general conditions (in particular (a) and (b) from Theorem I). The following theorem is a generalization of Rice's theorem. Theorem 2. Let $A$ be any nontrivial invariant (under extensional equality) property of (Gödelnumbers relative to $u$ of) members of $R$. Then property $A$ is unrecognizable by general recursive functions from $R$. The class of all primitive recursive functions and the Gnsegorchyk class $E^n$ (for any $n>1$) satisfy conditions of the theorem.