Computable trees, prime models, and relative decidability

Abstract:

We show that for every computable tree $\mathcal T$ with no dead ends and all paths computable, and every $D >_T \emptyset$, there is a $D$-computable listing of the isolated paths of $\mathcal T$. It follows that for every complete decidable theory $T$ such that all the types of $T$ are computable and every $D >_T \emptyset$, 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.