Доктор физико-математических наук, профессор, кафедра теоретической информатики, Центр интегрируемых систем.
Ул. Советская, 14, Ярославль, 150003
Valery Anatolyevich Sokolov - Doctor of Science, Professor, Department of Theoretical Informatics, Centre of Integrable Systems.
14 Sovetskaya, Yaroslavl 150003
Рафаэль Робинсон показал, что все примитивно рекурсивные функции, зависящие от одного аргумента, и только они могут быть получены из двух функций s(x) = х +1 и q(x) = x - [√x]²
с помощью операций сложения +, суперпозиции ∗ и итерации i. Джулия Робинсон доказала, что из этих же двух функций с помощью операций сложения +, суперпозиции ∗ и операции ¯¹ обращения функций можно получить все общерекурсивные (при определённом условии на операцию обращения) и все частично рекурсивные функции. На основании этих результатов А. И. Мальцев ввёл в рассмотрение алгебру Рафаэля Робинсона всех одноместных примитивно рекурсивных функций и две алгебры Джулии Робинсон: частичную алгебру всех одноместных общерекурсивных функций и алгебру всех одноместных частично рекурсивных функций, и предложил исследовать свойства этих алгебр, в том числе, выяснить, существуют ли в этих алгебрах конечные базисы тождеств. В этой статье мы показываем, что конечного базиса тождеств ни в одной из указанных алгебр не существует.
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 - [√x]² by using operations of addition +, superposition ∗ and iteration i. Julia Robinson proved that from the same two functions, using the addition +, superposition ∗ and operation ¯¹ 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.
The authors declare that there are no conflicts of interest present.