0
$\begingroup$

Okay so Ive got a problem with the "direction" of reduction and untimately the whole proof, reduction idea as a whole...

My Question is:

Prove that the problem of deciding whether a Turing Machine M halts on input w is undecidable. Use the fact that deciding whether a Turing Machine M accepts no input whatsoever, i.e., L(M ) = ∅, is undecidable.

Is this asking to show that deciding whether a Turing Machine M accepts no input whatsoever is undecidable? or that the halting problem is undecidable?

How do you approach such a proof?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.