# Is it undecidable if the language of a given Turing Machine is the set of composite numbers?

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?

• "Do I have to make multiple reductions?" -- you never have to, but it can be easier. – Raphael Aug 8 '16 at 8:40
• "contradictory argument" -- hopefully not; do you mean proof by contradiction? – Raphael Aug 8 '16 at 8:41
• I think this is a duplicate of our reference question. Community votes, please! – Raphael Aug 8 '16 at 8:41
• @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. – David Richerby Aug 8 '16 at 8:59
• @DavidRicherby I was thinking of the 30s solution with Rice's theorem, which answers both questions posted above with "no". – 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.