Preview

Моделирование и анализ информационных систем

Расширенный поиск

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

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

Полный текст:

Аннотация

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

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

Об авторе

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

Доктор физико-математических наук, профессор, кафедра теоретической информатики, Центр интегрируемых систем.

Ул. Советская, 14, Ярославль, 150003



Список литературы

1. A. I. Mal’tsev, "Constructive algebras I”, Russian Mathematical Surveys, vol. 16, no. 3, pp. 77-129,1961.

2. A. I. Mal’tsev, Algoritmy i rekursivnye funktsii. Moscow: Nauka, 1965, In Russian.

3. J. Robinson, "Primitive recursive functions”, Proceedings of the American Mathematical Society, vol. 1, no. 6, pp. 703-718, 1950.

4. R. M. Robinson, "Primitive recursive functions”, Bulletin of the American Mathematical Society, vol. 53, no. 10, pp. 925-942, 1947.

5. V. A. Sokolov, "Ob odnom klasse tozhdestv v algebre Robinsona”, in 14-ya Vsesoyuznaya algebraicheskaya konferentsiya: tezisy dokladov, In Russian, vol. 2, Novosibirsk, 1977, pp. 123-124.

6. P. M. Cohn, Universal Algebra. New York, Evanston, and London: Harper & Row, 1965.

7. A. Robinson, "Equational logic for partial functions under Kleene equality: a complete and an incomplete set of rules”, The Journal of Symbolic Logic, vol. 54, no. 2, pp. 354-362, 1989.


Для цитирования:


Соколов В.А. О проблеме существования конечных базисов тождеств в алгебрах рекурсивных функций. Моделирование и анализ информационных систем. 2020;27(3):304-315. https://doi.org/10.18255/1818-1015-2020-3-304-315

For citation:


Sokolov V.A. On the Existence Problem of Finite Bases of Identities in the Algebras of Recursive Functions. Modeling and Analysis of Information Systems. 2020;27(3):304-315. (In Russ.) https://doi.org/10.18255/1818-1015-2020-3-304-315

Просмотров: 147


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)