|
Zapiski Nauchnykh Seminarov 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.
Citation:
N. K. Kossovski, “On recognizing invariant properties of algorithms”, Studies in constructive mathematics and mathematical logic. Part V, Zap. Nauchn. Sem. LOMI, 32, "Nauka", Leningrad. Otdel., Leningrad, 1972, 29–34
Linking options:
https://www.mathnet.ru/eng/znsl2561 https://www.mathnet.ru/eng/znsl/v32/p29
|
Statistics & downloads: |
Abstract page: | 213 | Full-text PDF : | 79 |
|