# Deciding whether set of running times is infinite

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?

• If a language is in R, then in particular it is in RE. – Yuval Filmus Nov 3 '19 at 16:41
• Your solution idea makes me doubt you understand what it means for $L$ to be decidable. It means that given a description of a Turing machine, there is an algorithm that always halts and determines whether Count of the input machine is infinite or not. – Yuval Filmus Nov 3 '19 at 22:40
• I don't understand what you mean by "when $M$ halts on $w$ it halts after $k$ steps" -- either $M$ halts on $w$, or it doesn't. Do you mean "$M$ halts on $w$ after $k$ steps"? Or something else? – D.W. Nov 4 '19 at 8:16
• @D.W. Let $t(M,w)$ be the running time of $M$ on $w$ (possibly $t(M,w) = \infty$). Then $\mathrm{Count}(M) = \{t(M,w) : w \in \Sigma^*, t(M,w) < \infty\}$. – Yuval Filmus Nov 4 '19 at 11:41
• @YuvalFilmus, ok, cool, that makes sense. Can I encourage you to edit the question accordingly? – D.W. Nov 4 '19 at 17:56

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}$$.
• It's just a name for the number of steps that $M'$ will perform before halting when its input is a string of $s+1$ ones. – Steven Nov 4 '19 at 22:25