|
Theory of computing
On the existence problem of finite bases of identities in the algebras of recursive functions
V. A. Sokolov P. G. Demidov Yaroslavl State University, 14 Sovetskaya, Yaroslavl 150003, Russia
Abstract:
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.
Keywords:
algebras, recursive functions, identities, basis, superposition, iteration, function inversion.
Received: 21.08.2020 Revised: 07.09.2020 Accepted: 09.09.2020
Citation:
V. A. Sokolov, “On the existence problem of finite bases of identities in the algebras of recursive functions”, Model. Anal. Inform. Sist., 27:3 (2020), 304–315
Linking options:
https://www.mathnet.ru/eng/mais717 https://www.mathnet.ru/eng/mais/v27/i3/p304
|
Statistics & downloads: |
Abstract page: | 132 | Full-text PDF : | 53 | References: | 24 |
|