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$ – Yuval Filmus Nov 3 '19 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$ – Yuval Filmus Nov 3 '19 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 '19 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$ – Yuval Filmus Nov 4 '19 at 11:41
  • $\begingroup$ @YuvalFilmus, ok, cool, that makes sense. Can I encourage you to edit the question accordingly? $\endgroup$ – 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}$.

| cite | improve this answer | |
  • $\begingroup$ i really appreciate it! can you explain me what ℓ stands for? $\endgroup$ – Alon Amir Nov 4 '19 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 '19 at 22:25

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.