[SpeedisaVirus]

Hello,

I'm currently working on a homework assignment and I am being told to prove a language is not recursive. I can't fathom why it would not be.

The Q:
Prove L={M| L(M) accepts only even length strings} is not recursive.

I personally can't fathom how this is not a recursive language. To me it seems like it meets all of the requirements. For every string in the language it will be able to decide that it is either even length or odd length when it reaches the end, no? The same would be true of it's complement, correct? Shouldn't this indicate that it is in fact recursive? Why is it not recursive?

It just seems reasonable that it would always halt on an input. Maybe there is some lack of understanding here? I guess if the string was infinitely long it would never decide but is that part of the why?

This post has been edited by SpeedisaVirus: 15 May 2010 - 05:17 PM

[SpeedisaVirus]

Thinking...L(M) that accepts all even strings is decidable. Perhaps I am missing something in notation though. Perhaps this is saying that this is the language that accepts the machine that accepts all even strings which would them make this sort of a halting problem thing?

[mojo666]

I don't think this is as simple as finding a machine that accepts all even length strings. I'm reading "L={M| L(M) accepts only even length strings}" as "the set of all machines that only accepts even length strings". Note that "only accepting even length strings" is different from "accepting all even length strings". If you make a machine that accepts "00" and rejects all others then that would still be in L.

[mostyfriedman]

mojo is right..anyway at first sight, i could see that this language is undecidable because of what rice's theorem states.. anywayz, the proof of this by contradiction is pretty simple, think about it.