Получено отрицательное решение проблемы существования конечных базисов тождеств, определяющих многообразия, порождённые алгебрами одноместных рекурсивных функций. Показано, что в многообразиях алгебр, порождённых алгебрами примитивно рекурсивных и частично рекурсивных функций, не существует конечных базисов тождеств, определяющих эти многообразия. Для алгебры одноместных общерекурсивных функций, которая является частичной, аналогичная проблема решена в семантике Клини для тождеств.

рекурсивные функции

Соколов Валерий Анатольевич,  Ярославский государственный университет им. П.Г. Демидова