|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Математическая логика, алгебра и теория чисел
Безатомные булевы алгебры, вычислимые за полиномиальное время
П. Е. Алаев Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
Аннотация:
We construct an example of atomless Boolean algebra $ {\mathfrak B} $, computable in polynomial time, that has no primitive recursive function $ f : B \to B $ such that $ 0 < f (a) < a $ for $ a \neq 0 $. In addition, we show that if two primitive recursive atomless Boolean algebras $ {\mathfrak B}_{1} $ and $ {\mathfrak B}_{2} $ have such functions, then there is an isomorphism $ g : {\mathfrak B}_{1} \to {\mathfrak B}_{2} $ such that $ g $ and $ g^{-1} $ are primitive recursive functions.
Ключевые слова:
computable structure, Boolean algebra, primitive recursive structure, polynomial time computability, primitive recursive isomorphism.
Поступила 10 октября 2016 г., опубликована 22 ноября 2016 г.
Образец цитирования:
П. Е. Алаев, “Безатомные булевы алгебры, вычислимые за полиномиальное время”, Сиб. электрон. матем. изв., 13 (2016), 1035–1039
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr732 https://www.mathnet.ru/rus/semr/v13/p1035
|
Статистика просмотров: |
Страница аннотации: | 185 | PDF полного текста: | 51 | Список литературы: | 38 |
|