RUS  ENG
Full version
JOURNALS // Modelirovanie i Analiz Informatsionnykh Sistem // Archive

Model. Anal. Inform. Sist., 2020 Volume 27, Number 3, Pages 304–315 (Mi mais717)

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.

UDC: 512.57

MSC: 03D20

Received: 21.08.2020
Revised: 07.09.2020
Accepted: 09.09.2020

DOI: 10.18255/1818-1015-2020-3-304-315



© Steklov Math. Inst. of RAS, 2024