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:Halting problemBlank Tape Halting problemState-Entry problemIf a TM accepts nothingIf a TM accepts everythingI 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?
Is it undecidable if the language of a given Turing Machine is the set of composite numbers?
computability;turing machines;undecidability
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.