1
$\begingroup$

I have a problem with this task:

Show that this language is recursive enumerable, but not recursive: $L = \{ w \in \{0,1\}^* | M_w(x)\; \text{converges for some input}\; x \}$ (where $M$ is turing machine).

I know how to do it with this one: $L = \{ w\in \{0,1\}^* | w \in L(M)\;\text{for some TM $M$} \} \to$ complement of $L$ is diagonalization, so it is not accepted by any TM, so complement of $L$ is not recursively enumerable and so $L$ is not recursive.

Is there any similar approach for original task, please? Or do you have idea how to proceed?

  • 0
    For some basic information about writing math at this site see e.g. [here](http://meta.math.stackexchange.com/questions/5020/), [here](http://meta.stackexchange.com/a/70559/155238), [here](http://meta.math.stackexchange.com/questions/1773/) and [here](http://math.stackexchange.com/editing-help#latex).2012-11-06
  • 0
    I tried to improve your post using TeX (for better readability). Please check whether these edits did not unintentionally change the meaning of your post.2012-11-06
  • 0
    it's ok, thanks ... sorry about that, my first post ...2012-11-06
  • 0
    I know, no worries. Welcome to math.SE.2012-11-06
  • 0
    Am I right in guessing that $M_w$ is used to denote some enumeration of all Turing machines, as $w$ varies? Also, what is the meaning of convergence here?2012-11-06
  • 0
    yes, you are right... and convergence means that such a turing machine will one day terminates its computation2012-11-06

1 Answers 1

1

Say your $L$ was recursive. Then it's complement would also be recursive, i.e. the problem of whether some $M_w$ diverges for all inputs would be decidable.

Now, say you have a turing machine $M'$ and some input $x'$. You can then find some turing machine $M$ which first writes $x'$ to the tape (overwriting the previous input), and then continues as $M'$ would. $M$ diverges for all inputs exactly if $M'$ diverges for input $x'$. Thus, if you can decide whether or not a arbitrary turing machine $M$ diverges for all inputs, you can also decide whether an arbitrary machine terminates for some arbitrary input. Which you know that you cannot, since this is the halting problem. $L$ is thus not recursive.

$L$ is recursively enumerable, though, because you can simply interate over all triples $(M_w,x,n)$ (diagonally!) and check whether $M_x(x)$ converges after $n$ steps. If $w \in L$, you'll eventually reach the input $x$ for which it converges and some $n$ which is at least as large as the number of steps it takes for $M_w(x)$ to converge, thus discovering that $w \in L$.

  • 0
    Hey, thanks for very nice explanation! I think I get it now :)2012-11-06