3
$\begingroup$

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.

$\endgroup$

0

Your Answer

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