2
$\begingroup$

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.)

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why not True Arithmetic and just $\Pi_{17}$? And on that note, why not Zoidberg? $\endgroup$ – Asaf Karagila May 21 '18 at 17:58
  • $\begingroup$ @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.) $\endgroup$ – Noah Schweber May 21 '18 at 18:06
  • $\begingroup$ I'm confused. You're claiming to be a gentleman? Or better than Zoidberg? :P $\endgroup$ – Asaf Karagila May 21 '18 at 18:08
  • $\begingroup$ Cool. One consequence is that the set theoretic multiverse is not falsifiable via Turing machine (not that is was trying to be). $\endgroup$ – PyRulez May 21 '18 at 21:24
  • 1
    $\begingroup$ @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). $\endgroup$ – Noah Schweber May 21 '18 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.