RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2016, том 13, страницы 1035–1039 (Mi semr732)

Эта публикация цитируется в 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.

УДК: 510.5, 512, 510.6

MSC: 03C57, 03D15, 06E99

Поступила 10 октября 2016 г., опубликована 22 ноября 2016 г.

DOI: 10.17377/semi.2016.13.082



Реферативные базы данных:


© МИАН, 2024