[Tennenbaums' theorem](http://arxiv.org/abs/1311.6375) proves neither addition nor multiplication can be recursive in any countable [non-standard model of arithmetic](http://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic). Tennenbaum's proof applies to [theories much weaker than PA](http://www.math.cas.cz/~jerabek/papers/realclosures.pdf).


Tennenbaum's proof is a proof by contradiction. If addition or multiplication is recursive in a non-standard model then it is possible to prove recursively inseparable sets can be encoded as non-standard natural numbers. 


Let $\mathbb{N}^\*$ be a countable non-standard model of PA and let $\mathbb{Z}^\*$ be the integers extended from $\mathbb{N}^\*$. A "non-standard finite field" would be a ring $\mathbb{Z}^\* /p^\* \mathbb{Z}^\*$ where $p^\*$ is a non-standard prime larger than any standard natural number. It is straight forward to argue [Tennenbaum's theorem applies to non-standard finite fields](https://mathoverflow.net/questions/151871/recursive-non-standard-models-of-modular-arithmetic).


Ax has proven the [theory of finite fields is decidable](http://www.jstor.org/discover/10.2307/1970573?uid=2129&uid=2&uid=70&uid=4&sid=21103452330707). Non-standard finite fields admit [almost quantifier elimination](http://terrytao.wordpress.com/2012/09/12/definable-subsets-over-nonstandard-finite-fields-and-almost-quantifier-elimination/). If there exists a recursive non-standard finite field then Tennenbaum's proof by contradiction becomes a proof of contradiction. 


Is "almost quantifier elimination" enough to prove there exists a recusive non-standard finite field? Can a decidable theory have non-recursive models? If so, is there an algorithm to determine if a given model is recursive?


I previously asked [this question on Stack Exchange.](https://math.stackexchange.com/questions/633283/can-a-decidable-theory-have-nonrecursive-models)



Can a Decidable Theory Have Non-recursive Models?
A decidable theory can certainly have noncomputable models. For example, consider a theory with an infinite set of 0-ary relation symbols $A\_1, A\_2, \ldots$; no other relation, function, or constant symbols; and no axioms. This theory is decidable - it is basically just propositional logic - and its countable models are in effective correspondence with the subsets of $\mathbb{N}$ in the obvious way. 


There is not an algorithm, in general, to tell whether a subset of $\mathbb{N}$ is computable. The class of computable subsets of $\mathbb{N}$ is $\Sigma^0\_3$, strictly. 


