Program-closed classes of general recursive functions and predicates of finite rank (Q1902762)

We study a functional system consisting of the set of all one-place general recursive functions (GRF) and general recursive predicates (GRP) together with the operation of closure with respect to a class of standard program schemes enriched by massives (arrays) and by the equality predicate. In earlier papers, we described all the finitely generated pre-complete classes of such a functional system. We can say that a closed finitely generated class \({\mathfrak A}\) has finite rank \(k\) if there exists a sequence of finitely generated closed classes \({\mathfrak A}_k \varsubsetneq \ldots \varsubsetneq {\mathfrak A}_0\) such that \({\mathfrak A}_0\) is a complete class (all GRF and GRP), \({\mathfrak A}_k = {\mathfrak A}\), and \({\mathfrak A}_{i + 1}\) is pre-complete with respect to \({\mathfrak A}_i\) for any \(i \leq k - 1\), i.e., for any finitely generated closed class \({\mathfrak B}\) the inclusion \({\mathfrak A}_{i + 1} \subseteq {\mathfrak B} \subseteq {\mathfrak A}_i\) implies either \({\mathfrak A}_{i + 1} = {\mathfrak B}\) or \({\mathfrak A}_i = {\mathfrak B}\). According to \textit{V. M. Glushkov}, \textit{G. E. Tsejtlin} and \textit{E. L. Yushchenko} [Algebra. Languages. Programming. 2nd rev. ed. (Russian) (1978; Zbl 0405.68001)], the next intrinsic step in the investigation of these systems is a description of finitely generated closed classes of finite rank. The present article is devoted to this problem.