show L is re but not rec

Question

let L be language consisting of pair of tm codes and an integer (M1,M2,k) such that L(M1) intersect L(M2)contains atleast k strings show L is RE but not recursive

Answer 1

To Prove: $L$ is RE but not REC.

Proof:
Let a turing machine $M$ accepts the language $L$.

What that machine does is that for each set $\langle M_1, M_2, k \rangle$ (which is its own input) it simulates some strings on the machines $M_1$ and $M_2$ i.e. give a string at a time to both of them as input to those machines. If they accept atleast $k$ of those input strings presented by $M$ to them then we say, accepted and Halt our turing mahcine $M$.
So, Machine $M$ halts and accepts on all accepted inputs. Hence, $L$ is RE.

but, if no string is common to $M_1$ and $M_2$, say, input set is $\large \langle a^*, b^*, 7 \rangle$ then machine $M$ will never halt. it keeps feeding those machines $\infty$ input strings.
Hence, it does not halt on all strings which are not in the language. $\therefore \ L$ is not REC.

Hence, $L$ is RE but not REC.

Comments

$k = 0, M_2 = \Sigma^*$ make it decide if for a given TM, $L(M) = \emptyset.$

---

 halts and accepts on all accepted inputs

can be written as 

halts and accepts on all inputs which are to be accepted.  

Answer 2

What u can do

since k is any no.

take k length input run on turing machine after k step if o/p belongs to language the it is RE but when till k length not accept then you cant say it is rejected b/c TM can be go into loop after k step.

so we decide for only those string which are in language but not decide for which not belongs to language. so its Semi decidable i.e. RE

Comments

@arjun then i think it will be non re (mainly because of "atmost ")

---

By using Rice theorm

T yes phi and Tno everythng

Tyes   proper subset of Tno.

By using this method?????

---

yes, both are correct..

Answer 3

Logical Method

Take M1 & M2.

Run M1 & M2 each on all strings over alphabet given using dovetaling method (parallel running machine on multiple strings0

Then if M1 & M2 do accept k strings eventually you will say yes.

If they just keep running on all input, can you even say no ? Say it is been year & now you want to say no, can you ? NO, as maybe computation is just way too long, both might accept k strings in few minutes.. & So on. You will never know if the machines keep running forever.

So answering NO question is not possible.

So Recursive enumerable, but not recursive.

 

Ref -> https://en.wikipedia.org/wiki/Dovetailing_%28computer_science%29 , for Dovetaling