This is a practice question I have, but I can't wrap my head around it. ............. Let L = {M | M is a TM that halts with exactly two words on its tape in the form Bw1Bw2B}. B = Blank Position

the problem of deciding whether an arbitrary Turing machine will accept an arbitrary input, is undecidable. Use this result to prove, formally using problem reduction, that given an arbitrary Turing machine M, the problem of deciding if M ∈ L is undecidable. ............ I have no knowledge of proofs. I don't have a clue how to tackle this question, can someone point me to a tutorial that works with proofs by reduction along with Turing machines.


closed as unclear what you're asking by dkaeae, Yuval Filmus, Evil, David Richerby, Discrete lizard Sep 12 at 18:01

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ First and Second links from google $\endgroup$ – diplodoc Sep 11 at 10:47
  • 2
    $\begingroup$ If you have no knowledge of proofs, computability theory is not the perfect place to start. $\endgroup$ – Yuval Filmus Sep 11 at 12:15