[Solved]: Proving that a language of Turing machine descriptions is/is not Turing recognizable

Problem Detail: 

How to approach to solve this question and the likes of it?

Let $L$ be the set of strings $\langle M\rangle$ such that $M$ accepts all strings of even length and does not accept any strings of odd length.

a) Is $L$ Turing-recognizable? Prove your answer.
b) Is the complement of $L$ Turing-recognizable? Again prove your answer.

Please have a look at my approach, is it correct? :

Since the string representation of set of all the Turing Machines (say S) is Infinite countable and Recursively Enumerable, there fore there exists a Turing Machine that accepts S. Now, if we choose the Turing Machines M1, M2, ... from S, in the given order, such that all the chosen machines accept even length string and reject odd length strings, then the set we get (Say T) will also be Infinite Countable and recursively Enumerable and will have a Turing Machine which accepts it. That is why it is language T is Turing Recognizable. Similarly complement of T is Turing Recognizable.

@Rick if I use the following code :

RL(<M>) =   for n = 0, 1, ...      for s = s0, ..., sn  \\in the standard order on all strings        run M on s for one move          if M(s) = accept AND |s| is odd            reject // accept as string in L complement      if not rejected for any string then accept as a string in L 

This code will select all the $M$ which accept all strings of even length and do not accept any string of odd length. Then now since we have a membership algorithm for $L$ (as well as for $\overline L$), then can we say that the $L$ and $\overline L$ are recursive?

Asked By : cnova

Answered By : Rick Decker

The problem with your proposed algorithm is where you say

... choose the Turing Machines M1, M2, ... from S, in the given order, such that all the chosen machines accept even length string and reject odd length strings.

How are you going to do this? If you could, then you would have answered your original question, i.e., you've fallen into the trap of assuming what you want to prove.

In fact, your language $L$ isn't recursively enumerable.

---

There are at least two ways to show that $L$ isn't r.e.. I'll give one, but it requires that you be able to show that $L$ isn't recursive. Rice's theorem is an immediate way, but you don't know it yet, so you'll have to reduce it from a known non-recursive language like the Halting language. That's not hard, but I won't give it now. Just accept for the moment that $L$ is not recursive.

Suppose that we wrongly guessed that $L$ was recursive and we wanted to build a recognizer for it. One way is to simply dovetail all strings and test whether $M$ accepted any odd-length strings (so we'd know then if $M$ wasn't in $L$). This gives us a proposed recognizer for $L$:

RL(<M>) =   for n = 0, 1, ...      for s = s0, ..., sn  \\in the standard order on all strings        run M on s for one move          if M(s) = accept AND |s| is odd            reject 

If $M$ accepts any odd-length string, sooner or later this program will find it and so will be able to recognize that $M$ is not in $L$. Of course this isn't what we wanted: we need to make a program that recognized if a given $M$ is in $L$. However, all is not lost---simply by changing the "reject" to "accept" we would have made a recognizer for the complement, $\overline{L}$, so we've stumbled across the interesting fact that $\overline{L}$ is recognizable.

So what, you might ask? Remember, if a language $A$ and its complement, $\overline{A}$ are both r.e., then $A$ must be recursive. We just showed that $\overline{L}$ is r.e., so if $L$ was also r.e., then we could conclude that $L$ was recursive. However, you've accepted that $L$ is not recursive, so we must conclude that $L$ must not be r.e..

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48659