RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. LOMI, 1972 Volume 32, Pages 29–34 (Mi znsl2561)

On recognizing invariant properties of algorithms

N. K. Kossovski


Abstract: 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.



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025