On the existence problem of finite bases of identities in the algebras of recursive functions

V. A. Sokolov

Modelirovanie i analiz informacionnyh sistem, Tome 27 (2020) no. 3, pp. 304-315

Résumé

Raphael Robinson showed that all primitive recursive functions depending on one argument, and only they could be obtained from two functions $s(x) = x +1$ and $q(x) = x - [\sqrt x]^2$ by using operations of addition $+$, superposition $*$ and iteration $i$. Julia Robinson proved that from the same two functions, using the addition $+$, superposition $*$ and operation $^{-1}$ of function inversion, one could obtain all general recursive functions (under a certain condition on the inversion operation) and all partially recursive functions. On the basis of these results, A. I. Maltsev brought into consideration the Raphael Robinson algebra of all unary primitive recursive functions and two Julia Robinson algebras: the partial algebra of all unary general recursive functions and the algebra of all unary partially recursive functions and proposed to study the properties of these algebras, including the question of the existence of finite bases of identities in these algebras. In this article we show that there is no finite basis of identities in any of the indicated algebras.

Détail

Keywords: algebras, recursive functions, identities, basis, iteration, function inversion.
Mots-clés : superposition