×

zbMATH — the first resource for mathematics

Complexity of categorical theories with computable models. (Russian, English) Zbl 1097.03027
Algebra Logika 43, No. 6, 650-665 (2004); translation in Algebra Logic 43, No. 6, 365-373 (2004).
The main results of the article are as follows:
Theorem 1. For each natural number \(n\geq 1\), there exists an \(\aleph_1\)-categorical theory \(T\) of finite signature such that (1) the Turing degree of \(T\) equals \(\mathbf{0}^{(n)}\); (2) \(T\) has a computable model; (3) all countable models of \(T\) have computable isomorphic copies; (4) \(T\) is weakly minimal.
Theorem 2. For each natural number \(n\geq 1\), there exists an \(\aleph_0\)-categorical theory of finite signature which admits a computable model but has Turing degree equal to \(\mathbf{0}^{(n)}\).

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