×

zbMATH — the first resource for mathematics

The computable dimension of \(I\)-trees of infinite height. (Russian, English) Zbl 1096.03051
Algebra Logika 43, No. 6, 702-729 (2004); translation in Algebra Logic 43, No. 6, 393-407 (2004).
A tree with distinguished initial subtree is called an \(I\)-tree. The main result of the article asserts that every computable \(I\)-tree of infinite height has \(\omega\) computable isomorphic copies which are pairwise computably nonisomorphic; moreover, there exists an algorithm that, given a computable sequence of computable presentations of such a tree, produces a new computable isomorphic copy of this tree which is not computably isomorphic to it, i.e., the class of all computable presentations of any of such trees is effectively infinite. These results can be generalized to several distinguished initial subtrees.

MSC:
03D45 Theory of numerations, effectively presented structures
03C57 Computable structure theory, computable model theory
PDF BibTeX XML Cite
Full Text: DOI