Model completeness and relative decidability

We study the implications of model completeness of a theory for the effectiveness of presentations of models of that theory. It is immediate that for a computable model $$\mathcal {A}$$ of a computably enumerable, model complete theory, the entire elementary diagram $$E(\mathcal {A})$$ must be decidable. We prove that indeed a c.e. theory T is model complete if and only if there is a uniform procedure that succeeds in deciding $$E(\mathcal {A})$$ from the atomic diagram $$\varDelta (\mathcal {A})$$ for all countable models $$\mathcal {A}$$ of T. Moreover, if every presentation of a single isomorphism type $$\mathcal {A}$$ has this property of relative decidability, then there must be a procedure with succeeds uniformly for all presentations of an expansion $$(\mathcal {A},\mathbf {a})$$ by finitely many new constants.