I found myself doing an exercise where I could logically prove that both L and its complementary are in RE but not in REC. Since we've seen that this isn't possible, I'm doing something wrong, but I can't figure it out.
This was the exercise:
I have a property P = { L | L is in RE, the intersection between L and D is empty} where D is the set of strings with odd length.
I've proven using Rice's theorem that Lp is not in REC.
To prove that Lp is in RE I thought of building an NTM N s.t. L(N)=Lp:
- take enc(M) as input and using the Universal TM I simulate M inside of N
- using non-determinism guess an odd length string w and simulate M on w
- if M accepts, then there exists an odd length string in L(M), so N rejects
On the other hand, I can build an NTM similarly s.t. L(N) is the complementary of Lp (by guessing an odd length string and accepting whether M accepts)
The complementary of P should be { L | L is in RE, L has at least one odd length string }
Since Lp is not in REC, both Lp and its complementary cannot be both in RE, or they would be in REC.
Could anyone tell me where I'm wrong?
The problem in your message is the proof that Lp is in RE.
You say: if M accepts, then there exists an odd length string in L(M), so N rejects. But you do not specify when N accepts. In fact there is no effective criterion for N to accept input enc(M) ... think about it and you will see that nothing works for acceptance.