# 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
Full Text: