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:
EQT M = {⟨M1, M2⟩ | L(M1) = L(M2)}.
I claim that this set is neither CE nor co-CE. Recall that the set AT M is not decidable but it is CE. Recall also that a set is decidable if it is both CE and co-CE, so AT M is not co-CE. Its complement AT M is co-CE but not CE. First, I will show that AT M ≤m EQT M , which will establish that EQT M 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 ̸∈ 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 ̸= w then M2 accepts it, ifx=wthenM2 simulatesMonwandacceptswifMdoes. Inthiscase⟨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