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

Аннотация

Рафаэль Робинсон показал, что все примитивно рекурсивные функции, зависящие от одного аргумента, и только они могут быть получены из двух функций s(x) = х +1 и q(x) = x - [√x]²

с помощью операций сложения +, суперпозиции ∗ и итерации i. Джулия Робинсон доказала, что из этих же двух функций с помощью операций сложения +, суперпозиции ∗ и операции ¯¹ обращения функций можно получить все общерекурсивные (при определённом условии на операцию обращения) и все частично рекурсивные функции. На основании этих результатов А. И. Мальцев ввёл в рассмотрение алгебру Рафаэля Робинсона всех одноместных примитивно рекурсивных функций и две алгебры Джулии Робинсон: частичную алгебру всех одноместных общерекурсивных функций и алгебру всех одноместных частично рекурсивных функций, и предложил исследовать свойства этих алгебр, в том числе, выяснить, существуют ли в этих алгебрах конечные базисы тождеств. В этой статье мы показываем, что конечного базиса тождеств ни в одной из указанных алгебр не существует.