Reduction from $\mathsf{ALL}_{\mathsf{TM}}$ to it's complement

Question

I'd like to know if there's a reduction $\mathsf{ALL}_{\mathsf{TM}}\leq_{m}\overline{\mathsf{ALL}_{\mathsf{TM}}}$ where of course $\mathsf{ALL}_{\mathsf{TM}}=\left\{ \left\langle M\right\rangle \mid\mathsf{L}\left(M\right)=\Sigma^{*}\right\} $

All attempts I've tried failed - if for example I try to define the reduction by switching the accept state and the reject state, the construction fails because it doesn't take care of the case where the machine doesn't halt.

Answer 1

The main problem here is that we cannot express either ALL or it's complement by a TM. There are no enumerater for these sets. So we need to use an oracle to be able to express these sets by an oracle TM.

Consider the following set:

K = {<e,i> | e is code of a TM that halts with input i.}

Using an oracle for K we can make the following program for enumerating ALL's complement:

for each e (e is code of a TM):

Look for a number say d such that <e,d> doesn't belong to K.

If there is such an d, print e.

After here, when I say oracle, I mean an oracle for K:

Let's say that ALL is many one reducible to its complement. Then according to properties of many one reduction, ALL's complement being enumerabe by an oracle TM implies that ALL is enumerabe by an oracle TM. So ALL is decidable using an oracle TM.

Now let e be code of the oracle TM which decides ALL. We define the following machine:

For input i: If i belongs to ALL, Run i's machine on i as input. Add one to result and return the final number.

Otherwise, halt and print 0.

Now, if e0 is code of the TM described above, what would be the result of giving this TM its own code?

Then we have that result of running i's machine on i as input is same as result of adding one to result of running i's machine with i as input!

We get into an contradiction. So ALL is not decidable using an oracle for K. So our previous hypothesis which states that ALL is many one reducible to its complement is false.

Answer 2

A mapping reduction doesn't exist. A proof using the recursion theorem goes as follows.

Suppose a mapping reduction exists, and let $f$ be the mapping. Construct the TM

$R$ = "On input $x$,

1. Get the description $\langle R\rangle$ of itself from the recursion theorem.
2. Get $\langle R'\rangle = f(\langle R\rangle)$.
3. Simulate $R'$ on $x$."

Then $L(R) = L(R') = L(f(R))$, so $R$ and $f(R)$ must both be in $ALL_\mathsf{TM}$ or both not in it, contradicting the assumption that $f$ is a mapping reduction from $ALL_\mathsf{TM}$ to its complement.