What I mean is this. By downward Lowenheim-Skolem theorem, first-order formula Q is a always true iff it is true in every countable structure. But is there some first-order formula Q which is true in every computable structure and false in some non-computable structure? My feeling is that of course the answer should be "yes", but I can't construct an example. I feel also that the questions of the sort has been widely studied. (For example, maybe some study of conditions under which first-order theory has computable model or hasn't). Do you know anything about that?


Thanks in advance.



Are computable models sufficient?
There is no computable, countable nonstandard model of Peano arithmetic. This result is known as Tennenbaum's theorem after Stanley Tennenbaum. There is an online paper at [1]. So if you take any sentence $R$ in the language of PA that is not true in the standard model but is consistent with PA, it will be true in some countable model of PA but not in the (unique, up to isomorphism) computable model of PA. 


But I'm not sure if that addresses your question, because that answer is about models of a theory. In your question, it seems like you're talking about all countable models in the language of particular formula, rather than all models of a particular theory. 


To make the answer fit that question, we want to replace PA with a finitely axiomatized subtheory of PA for which the only computable model is the standard model. There is a heuristic principle that we should be able to find a subtheory like this by examining the proof of Tennenbaum's theorem, and reference [1] confirms that this does work.


Let $T$ be the sentence that is the conjunction of the axioms of this subtheory. Let $R$ be the independent sentence from the first part, and look at the sentence $T \rightarrow \lnot R$. This will be true in every computable model (because the only computable model that satisfies $T$ is the standard model, which satisfies $\lnot R$). It will be false in any countable nonstandard model of PA in which $R$ holds, because $T$ is a subtheory of PA. 


1: Richard Kaye, "Tennenbaum's Theorem for Models of Arithmetic", <http://web.mat.bham.ac.uk/R.W.Kaye/papers/tennenbaum/tennenbaum>


(Note: I corrected the last paragraph based on a comment by Sergei Tropanets.)


