О проблеме существования конечных базисов тождеств в алгебрах рекурсивных функций

Рафаэль Робинсон показал, что все примитивно рекурсивные функции, зависящие от одного аргумента, и только они могут быть получены из двух функций $s(x) = х +1$ и $q(x) = x - [\sqrt x]^2$ с помощью операций сложения $+$, суперпозиции $*$ и итерации $i$. Джулия Робинсон доказала, что из этих же двух функций с помощью операций сложения $+$, суперпозиции $*$ и операции $^{-1}$ обращения функций можно получить все общерекурсивные (при определённом условии на операцию обращения) и все частично рекурсивные функции. На основании этих результатов А. И. Мальцев ввёл в рассмотрение алгебру Рафаэля Робинсона всех одноместных примитивно рекурсивных функций и две алгебры Джулии Робинсон: частичную алгебру всех одноместных общерекурсивных функций и алгебру всех одноместных частично рекурсивных функций, и предложил исследовать свойства этих алгебр, в том числе, выяснить, существуют ли в этих алгебрах конечные базисы тождеств. В этой статье мы показываем, что конечного базиса тождеств ни в одной из указанных алгебр не существует.