I want to make the following reduction:

HP is the Halting Problem: HP = {w#x | w, x ∈ {0,1}* , Mw halts on input x} w is the binary coded turing machine Mw. L3 is the problem which asks, if M accepts exactly 3 inputs.

I know HP is not decidable, so I want to show that L3 is not decidable also:

HP ≤ L3

How can I make the reduction? The problem is that I don't know how I should proof that L3 accepts exactly just 3 inputs.

  • $\begingroup$ You can use Rice's theorem. $\endgroup$ – Yuval Filmus Jul 7 '18 at 21:03
  • $\begingroup$ Yes because the 3 inputs are not a non-trivial characteristic, you are right. But what if I want to show the reduction. I'm really wondering about how to solve it. $\endgroup$ – pjs Jul 7 '18 at 21:20
  • $\begingroup$ Repeat the proof of Rice's theorem, with your language replacing the arbitrary non-trivial language in the theorem. $\endgroup$ – Yuval Filmus Jul 7 '18 at 21:22
  • $\begingroup$ I'm sorry I cannot follow you. I was thinking about creating a Turing Machine Mw' running Mw as a subroutine. $\endgroup$ – pjs Jul 7 '18 at 21:30

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.