A set that is neither CE nor co-CE
Prakash Panangaden
22nd March 2021
Proposition 1. If Q ≤m P and if P is CE then so is Q. If P is co-CE so is Q.
Proof . Suppose that f is the required mapping reduction: then w ∈ Q if and only if f(w) ∈ P .
Now assume that P is CE. If I want to know whether w ∈ Q I will ask the algorithm for P if
f(w) ∈ P , if (w) ∈ P I will eventually find this out but if it is not, the algorithm may loop forever.
If P is co-CE I have an algorithm B with the property that for any word not in P the algorithm
will eventually tell me that it is not in P ; for words that are in P the algorithm may loop forever.
Now I want to know if w ∈ Q, I ask B if f(w) ∈ P , if it is not then I will find out eventually but
if it is in P B may loop forever. Thus Q is also co-CE.
Corollary 2. If Q ≤m P and if Q is not CE then neither is P .
Proof . This is just the contrapositive of the proposition.
Now for the main point of this note. Consider the set:
EQTM = {〈M1, M2〉 | L(M1) = L(M2)}.
I claim that this set is neither CE nor co-CE. Recall that the set ATM is not decidable but it is CE.
Recall also that a set is decidable if it is both CE and co-CE, so ATM is not co-CE. Its complement
ATM is co-CE but not CE. First, I will show that ATM ≤m EQTM , which will establish that EQTM
is not CE. Then I will show that ATM ≤m EQTM , which will show that EQTM is not co-CE.
To show the first claim we proceed as follows. Suppose I want to know whether w 6∈ L(M) for some
Turing machine M . Define two Turing machines M1 and M2 as follows. M1 rejects everything,
thus L(M1) = ∅. M2 checks if the input word is w, if it is not M2 will reject it. If the input word
is w then M2 simulates M on w: if M accepts w then M2 will as well. Thus 〈M, w〉 ∈ ATM if
and only if L(M1) = L(M2). Thus if EQTM is CE then so is ATM ; but we know that the latter is
not.
To show the second claim we proceed as follows. This time I want to know if w ∈ L(M). I define
M1 to accept everything and M2 as follows. M2 checks its input x: if x 6= w then M2 accepts it,
if x = w then M2 simulates M on w and accepts w if M does. In this case 〈M,w〉 ∈ ATM iff
L(M1) = L(M2). Thus if EQTM is co-CE so is ATM but we know that ATM is not co-CE.
1