Need help to check/extend a proof.
- From: Zenith <s.zenith.lee@xxxxxxxxx>
- Date: Tue, 18 Sep 2007 16:52:01 -0000
Another question from the archive:
L = {<M1><M2><M3>|L(M1)!=L(M2) and L(M2)!=L(M3) and L(M1)!=L(M3)}
Is this recursive? RE but not recursive? Not RE?
<Mi> is the encoding of TM Mi.
I started my proof with a 2 machine case:
We know that
1. L2 = {<M1><M2>|L(M1)=L(M2)} is undecidable
2. L2' = {<M1><M2>|L(M1)!=L(M2)} is the complement of L2
So we know that L2' is not recursive. I try to proof that L2' is RE:
To prove L(M1)!=L(M2), we only need one string that L(M1) accepts and
L(M2) does not.
So we construct a non-deterministic TM M-sim that simulates M1 and M2
in parallel. The input to M-sim is <M1><M2>. The simulated M1 and M2
uses a "guessed" (non-deterministic) string w as input. M-sim only
accepts if for some w, M1 or M2 goes to the accepting state but not
both.
Thus L(M-sim) = L2', and L2' is RE.
Is this proof correct?
If so, is it trivial to extend it to the three-machine case?
Thanks for any reply.
.
- Prev by Date: GREAT OPPURTUNITIES FOR INTERNSHIP CANDIDATES FOR FINAL YEAR CANDIDATES FOR M.TECH/B.E/MCA/BCA(CSE/ISE).
- Next by Date: What is the probability that a random graph contains an independent set of size at least j ?
- Previous by thread: GREAT OPPURTUNITIES FOR INTERNSHIP CANDIDATES FOR FINAL YEAR CANDIDATES FOR M.TECH/B.E/MCA/BCA(CSE/ISE).
- Next by thread: What is the probability that a random graph contains an independent set of size at least j ?
- Index(es):