No label defined (Q4946095)

It is known that every computable Boolean algebra is computably isomorphic to a polynomial-time Boolean algebra. The present paper studies the validity of this result in the case where the universe of the polynomial-time Boolean algebra is required to be in one of the following two forms: \(\text{Bin}(\omega)\), the set of natural numbers in binary representation, and \(\text{Tal}(\omega)\), the set of natural numbers in tally representation. The main results establish some conditions under which the computably isomorphim holds. For example, it is proved that if \(B\) is a countably infinite computable Boolean algebra such that both the set of atoms of \(B\) and the ideal generated by the atoms of \(B\) are computable, then \(B\) is computably isomorphic to a polynomial-time Boolean algebra with universe \(\text{Bin}(\omega)\) and to a polynomial-time Boolean algebra with universe \(\text{Tal}(\omega)\). For the entire collection see [Zbl 0923.00014].