I am aware that the following problems are undecidable and tried to reduce the given problem to one of the following but with no success:

  1. Halting problem
  2. Blank Tape Halting problem
  3. State-Entry problem
  4. If a TM accepts nothing
  5. If a TM accepts everything

I am looking for hints :)

Do I have to make multiple reductions?

Do I have to make a contradictory argument like we do for the Halting Problem?

  • $\begingroup$ "Do I have to make multiple reductions?" -- you never have to, but it can be easier. $\endgroup$ – Raphael Aug 8 '16 at 8:40
  • 1
    $\begingroup$ "contradictory argument" -- hopefully not; do you mean proof by contradiction? $\endgroup$ – Raphael Aug 8 '16 at 8:41
  • 1
    $\begingroup$ I think this is a duplicate of our reference question. Community votes, please! $\endgroup$ – Raphael Aug 8 '16 at 8:41
  • $\begingroup$ @Raphael I see your point but I think this one should be kept open, since the asker knows that reductions can solve the problem but needs more detailed help that's specific to this particular language. $\endgroup$ – David Richerby Aug 8 '16 at 8:59
  • 1
    $\begingroup$ @DavidRicherby I was thinking of the 30s solution with Rice's theorem, which answers both questions posted above with "no". $\endgroup$ – Raphael Aug 8 '16 at 9:10

Hint 1: Do you know Rice's theorem? It's the go-to result for any version of "Prove it's undecidable whether $L(M) =\,$ something."

Hint 2: You can reduce from "Does this TM accept everything?" You're given a Turing machine $M$ and you want to produce a new machine $T$ such that $T$ accepts the set of composites iff $L(M)=\Sigma^*$. Have $T$ reject its input if it's prime. If the input is composite, use its factors to decide what input you'll feed to $M$. You need to do this in a way that every possible input to $M$ corresponds to some combination of factors of $T$'s input.

Hint 2.5: Alternatively, go from "Does this TM accept nothing?" Similar idea but now $T$ will accept if its input is composite and you'll use prime inputs to $T$ to code inputs to $M$. Actually, this one might be slightly easier to see.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.