2

I have the following language:

$$L=\{\langle M1\rangle,\langle M2\rangle: |L(M_1) ∩ L(M_2)|≤10 ~~\text{ or }~~ |L(M_1) ∩ L(M_2)|≥1000\}$$

I am told that this language is either r,re or co-re. it was obvious that it is not in r.

I used a reduction to prove it is not in re.

My question is: how would one go about proving it is in co-re without reductions, or how would you go about creating a Turing machine that accepts the complement or rejects L.

(Note: to me this looks to not be in either re or co-re, but in the question, I am asked to identify it to be in either r, re or co-re).

emacs drives me nuts
  • 10,390
  • 2
  • 12
  • 31
yos_sir
  • 43
  • I'm inclined to agree with you that this is neither r.e. nor co-r.e., but maybe there's some tricky aspect that I've overlooked. Have you tried to prove that it's no co-r.e.? – Andreas Blass Aug 11 '22 at 20:20
  • @AndreasBlass tried to come up with a reduction to prove it is at least bigger then the union of re and co-re but did not manage as it is easy to prove it is in the union. I will try that for a bit more later but if you have any clue or idea i would love if you would share it :) – yos_sir Aug 12 '22 at 10:16
  • 1
    Given an arbitrary Turing machine $T$ and input $x$, construct $M_1$ and $M_2$ so that $|L(M_1)\cap L(M_2)|$ is always bigger than $10$ but is $\geq1000$ if and only if $T$ on input $x$ halts. That would give a reduction of the halting problem to your set, and you'd be done because the halting problem is not co-r.e. – Andreas Blass Aug 12 '22 at 13:39
  • @AndreasBlass you are absolutely right, thanks! – yos_sir Aug 15 '22 at 17:13

0 Answers0