Deciding whether set of running times is infinite

Question

I have a language $\mathrm{Count}(M)$, defined below, and a finite number $k$.

\begin{align} \mathrm{Count}(M)= \{k \in \mathbb{N} \mid \text{there exists some input on which $M$ halts after exactly $k$ steps}\}. \end{align}

I need to check whether the language $L$ is in RE, and whether it is in R. $$L= \{ \langle M \rangle \mid \text{$\mathrm{Count}(M)$ is an infinite set}\}.$$

My idea for a solution starts with: even though $L$ is an infinite language, it contains $\mathrm{Count}(M_i)$ that halts eventually. Each $M$ in $L$ must halt, and $\mathrm{Count}(M)$ is infinite.

So, in order to prove that $L$ is in RE, can I simply say every $M$ in $L$ halts eventually?

Answer 1

Suppose $L \in \textrm{RE}$. Given a Turing machine $M$ you can construct another Turing machine $M'$ that takes an input $x$ and simulates $M$ on an empty input for at most $|x|$ steps.

If $M$ eventually halts, say after $c$ steps, $M'$ will always halt after at most $f(c)$ steps, (for some function $f$), regardless of the choice of $x$. This shows that $\textrm{Count}(M') \subseteq \{ 1, \dots, f(c) \}$ is a finite set.

If $M$ does not halt, then $M'$ will halt after simulating $|x|$ steps of $M$ for every choice of $x$. By picking different values of $x$ it is possible to build an infinite set of inputs such that each input results in a different running time of $M'$ (e.g, start with $x=$"1" and let $s$ be the number of steps taken by $M'$ on input $x$. The next value of $x$ will be a string of $s+1$ ones, so that $M'$ necessarily halts after some number $\ell$ of steps such that $\ell \ge s+1$. The next value of $x$ will have $\ell+1$ ones, and so on).

This shows that $\textrm{Count}(M')$ is an infinite set.

Therefore, since $L \in \textrm{RE}$ you have just found a way to accept all (and only) the Turing machines $M$ that do not halt on an empty input, showing that the complement of the halting problem is in $\textrm{RE}$. This is a contradiction as it would imply that the halting problem is in $\textrm{R}$.