1
$\begingroup$

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?

$\endgroup$
  • 6
    $\begingroup$ What have you tried? Where did you get stuck? Are you familiar with the concept of reductions, and with Rice's theorem? $\endgroup$ – Shaull Oct 24 '15 at 11:22
  • $\begingroup$ @Shaull I've edited the question to include my approach. Please have a look at it. And No, I am not familiar with these concepts, any good read you recommend to understand them? $\endgroup$ – cnova Oct 24 '15 at 17:24
  • 2
    $\begingroup$ Please note that this is a question and answer site, not a discussion forum. Just one question at a time, please, and we're not here to grade your solution attempts. $\endgroup$ – David Richerby Oct 26 '15 at 0:21
  • $\begingroup$ @DavidRicherby Please note that I gave my solution after Shaull asked that what I had tried. And I wrote it in the question because I was unable to write it in the comment due to character limit constraint. And the second question was actually a doubt in the solution that Rick gave. Same reason to write it in the post. $\endgroup$ – cnova Oct 26 '15 at 15:09
  • $\begingroup$ @cnova OK -- it can be hard to figure that out when you just see the end result. $\endgroup$ – David Richerby Oct 26 '15 at 17:20
1
$\begingroup$

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..

$\endgroup$
  • $\begingroup$ Thanks for the answer, I think I understand what you are saying, but I have some doubts. One of which I have updated in the question Please clear it. $\endgroup$ – cnova Oct 24 '15 at 23:26

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.