# Is there a countable computably saturated model of ZFC that correctly solves the halting problem?

We say that a model of ZFC $M$ correctly solves that halting problem if for every turing machine $T$, $T\text{ halts} \iff M \models T \text { halts}$.

Is there a countable computably saturated model of ZFC which correctly solves the halting problem? (See pg 3 of https://arxiv.org/pdf/1104.4450.pdf for what computably saturated means.)

## 1 Answer

Sure. Any (consistent) theory (in a computable language) has computably saturated models, so just take $T$ to be (say) the theory ZFC + all true $\Pi_{17}$ statements of arithmetic. $T$ correctly decides (among other things!) whether the $e$th Turing machine halts, for each standard $e$, so any model of $T$ correctly solves the halting problem; now simply take an arbitrary computably saturated model of $T$.

Why do all appropriate theories have computably saturated models? Well, the point is that we only have to realize countably many types. Start with an arbitrary countable model $M$ of the theory, and list the computable types; at stage $s$, pass from the current model to a countable elementary extension realizing the $s$th computable type of that type is finitely consistent with the current model, and otherwise don't change the model - the union of this elementary chain will be a saturated model of the theory.

• Why not True Arithmetic and just $\Pi_{17}$? And on that note, why not Zoidberg? – Asaf Karagila May 21 '18 at 17:58
• @AsafKaragila A gentleman doesn't invoke TA unless it's absolutely necessary. And Zoidberg is no gentleman - just look at all the times he's invoked TA when it's not absolutely necessary! (I mean, sure, they all happened off-screen, but that's no excuse for rude logic.) – Noah Schweber May 21 '18 at 18:06
• I'm confused. You're claiming to be a gentleman? Or better than Zoidberg? :P – Asaf Karagila May 21 '18 at 18:08
• Cool. One consequence is that the set theoretic multiverse is not falsifiable via Turing machine (not that is was trying to be). – PyRulez May 21 '18 at 21:24
• @PyRulez On the contrary - in the first-order sense, the natural numbers not be well-orderable doesn't by itself have any implications for arithmetic: just consider a nonstandard elementary extension of $\mathbb{N}$ (which exists by compactness). – Noah Schweber May 21 '18 at 23:05