# Induction and nonstandard halting times of standard machines

For a nonstandard model of enough arithmetic - say, $\mathcal{N}\models I\Sigma_1$ - we can define the set of halting times of standard machines relative to $\mathcal{N}$: $$SH(\mathcal{N})=\{n\in\mathcal{N}:\exists e\in\omega(\mathcal{N}\models \text{\Phi_e(0) halts in exactly n steps})\}.$$ Here $\omega$ denotes standard $\omega$, so $SH(\mathcal{N})$ is not in general definable in $\mathcal{N}$. Note that $SH(\mathcal{N})$ is a subsemiring of $\mathcal{N}$, so we can consider it as a possible setting for arithmetic.

Sadly, $SH(\mathcal{N})$ is not guaranteed to be a model of $I\Sigma_1$, regardless of how much induction we have in $\mathcal{N}$. To see why: Suppose we have a $\Sigma_0$-formula $\varphi$ such that $SH(\mathcal{N})\models \exists x\varphi(x).$ Then certainly $\mathcal{N}\models\exists x\varphi(x)$, so there is a least $m\in\mathcal{N}$ such that $\mathcal{N}\models\varphi(m)$; however, this doesn't give us a least element of $SH(\mathcal{N})$ satisfying $\varphi$.

I'm in general interested in the arithmetic properties of $SH(\mathcal{N})$. In the interests of asking a concrete question, however:

Are there nonstandard models $\mathcal{N}$ of $I\Sigma_1$ with $SH(\mathcal{N})\models I\Sigma_1$? If so, what determines whether $SH(\mathcal{N})\models I\Sigma_1$?

• Is there any reason to believe $SH(\mathcal N)$ is different from the parameter-free $\Sigma_1$-definable elements on $\mathcal N$? – François G. Dorais May 22 '15 at 2:13
• No, they should be the same - that's a much clearer way to phrase it. – Noah Schweber May 22 '15 at 2:15

[Remark: This answer assumes Noah's answer to my comment that $SH(\mathcal N)$ consists precisely of the elements of $\mathcal N$ that are $\Sigma_1$-definable without parameters. This way, not only is $SH(\mathcal N)$ a semiring but it is closed under all standard primitive recursive functions (assuming $\mathcal N \models I\Sigma_1$). In particular, $SH(\mathcal N)$ understands the standard methods for encoding Turing machines and their computations, hence $SH(\mathcal N)$ correctly understands the formula $\tau(e,s)$ below.]
There is a bounded formula $\tau(e,s) \equiv$ "$\phi_e(0)$ halts in at most $s$ steps". Therefore $$\omega = \{x \in SH(\mathcal N) : SH(\mathcal N) \models \exists s \forall e \leq x \lnot\tau(e,s)\}$$ witnesses the failure of $\Sigma_1$-induction in $SH(\mathcal N)$ unless $SH(\mathcal N) = \omega$. The latter happens if and only if $\mathcal N$ satisfies every true $\Pi_1$ sentence.
• François, could you explain a bit more? Why doesn't $s=0$ fulfill that existential trivially? – Joel David Hamkins May 22 '15 at 12:13
• @JoelDavidHamkins: You're right that $SH(\mathcal N)$ depends on how one clocks Turing machines. If $0 \notin SH(\mathcal N)$ then $SH(\mathcal N)$ isn't a semiring nor does it contain all parameter-free $\Sigma_1$-definable elements of $\mathcal N$ and the answer breaks down. – François G. Dorais May 22 '15 at 17:00