##
Computable Trees, Prime Models, and Relative Decidability

Status: published in the *Proceedings of the American Mathematical
Society* vol. 134 (2006), pp. 1495 - 1498.

Availability: PostScript, DVI, and PDF

**Abstract.** We show that for every computable tree *T* with no
dead ends and all paths computable, and every noncomputable *D*,
there is a *D*-computable listing of the isolated paths of *T*.
It follows that for every complete decidable theory *T* such that all
the types of *T* are computable and every noncomputable *D*,
there is a *D*-decidable prime model of *T*. This result extends
a theorem of Csima and yields a stronger version of the theorem, due
independently to Slaman and Wehner, that there is a structure with
presentations of every nonzero degree but no computable presentation.

drh@math.uchicago.edu