  We discuss the complexity of completions of partial combinatory algebras, in
particular of Kleene's first model. Various completions of this model exist in
the literature, but all of them have high complexity. We show that although
there do not exist computable completions, there exists completions of low
Turing degree. We use this construction to relate completions of Kleene's first
model to complete extensions of PA. We also discuss the complexity of pcas
defined from nonstandard models of PA.

Logic;Logic in Computer Science