1
$\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.

Improve this question
$\endgroup$

0

Reset to default

Your Answer

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