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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.