On Degrees of Uncountably Categorical
Theories with Computable Models
Ekaterina Fokina (e_fokina@ngs.ru)
Novosibirsk State University (Russia)
One of the themes of computable model theory is concerned with the
following two questions. Let T be a first order consistent
theory. Does there exist a computable model of T? If T has a
computable model then what is the Turing degree of T? It's well
known that if T is decidable then T has a decidable model. On
the other hand, if theory T has a computable model then T is
computable in 0w. Goncharov and Khoussainov
proved that for any natural number n ³ 1, there exist
À1 -categorical computable models with the theories
Turing equivalent to 0n. We use a modified
construction to obtain the following result.
Any arithmetical Turing degree can be realized as the
computability-theoretic complexity of À1 -categorical
theory with computable model.
File translated from TEX by TTH, version 1.59.