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?

  • $\begingroup$ If a language is in R, then in particular it is in RE. $\endgroup$ Nov 3, 2019 at 16:41
  • $\begingroup$ 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. $\endgroup$ Nov 3, 2019 at 22:40
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Nov 4, 2019 at 8:16
  • $\begingroup$ @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\}$. $\endgroup$ Nov 4, 2019 at 11:41
  • $\begingroup$ @YuvalFilmus, ok, cool, that makes sense. Can I encourage you to edit the question accordingly? $\endgroup$
    – D.W.
    Nov 4, 2019 at 17:56

1 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}$.

  • $\begingroup$ i really appreciate it! can you explain me what ℓ stands for? $\endgroup$
    – Alon Amir
    Nov 4, 2019 at 22:17
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Nov 4, 2019 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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