Моделирование и анализ информационных систем
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Модел. и анализ информ. систем:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Модел. и анализ информ. систем, 2020, том 27, номер 3, страницы 304–315 (Mi mais717)  

Theory of computing

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

В. А. Соколов

Ярославский государственный университет им. П. Г. Демидова, ул. Советская, 14, г. Ярославль, 150003 Россия

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

Ключевые слова: алгебры, рекурсивные функции, тождества, базис, суперпозиция, итерация, обращение функции.

Финансовая поддержка Номер гранта
НИР ВИП-004 АААА-А16-116070610022-6
Инициативная НИР ВИП-004 (номер госрегистрации АААА-А16-116070610022-6).


DOI: https://doi.org/10.18255/1818-1015-2020-3-304-315

Полный текст: PDF файл (3780 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 512.57
MSC: 03D20
Поступила в редакцию: 21.08.2020
Исправленный вариант: 07.09.2020
Принята в печать:09.09.2020

Образец цитирования: В. А. Соколов, “О проблеме существования конечных базисов тождеств в алгебрах рекурсивных функций”, Модел. и анализ информ. систем, 27:3 (2020), 304–315

Цитирование в формате AMSBIB
\RBibitem{Sok20}
\by В.~А.~Соколов
\paper О проблеме существования конечных базисов тождеств в алгебрах рекурсивных функций
\jour Модел. и анализ информ. систем
\yr 2020
\vol 27
\issue 3
\pages 304--315
\mathnet{http://mi.mathnet.ru/mais717}
\crossref{https://doi.org/10.18255/1818-1015-2020-3-304-315}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais717
  • http://mi.mathnet.ru/rus/mais/v27/i3/p304

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
    Исправления
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:17
    Полный текст:2
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021