# Decidability of the minimum number of states a Turing Machine needs to accept a language

I'm reading some old notes from a course on Turing Machines and I've bumped into the following question:

Is the following language decidable? The language formed by the set of all Turing Machines whose languages can be accepted by a Turing Machine with at most 37 states

My assumption is that the question boils to whether, for a given Turing Machine, there exists an algorithm to minimise its number of states. In that case, we could run the algorithm against a given machine M, and if the number of states is greater than 37, it doesn't belong to the language; otherwise, it does.

The question then boils to whether such an algorithm exists. I have not found anything about that in the notes nor online.

Hint:

How many states does it take to recognize the language $$\Sigma^*$$?

A further hint:

Is it easy or hard to test whether a given Turing machine accepts $$\Sigma^*$$?

• I appreciate not trying to spoil the spirit of homework, but I have to say it's not an assignment and the course is no longer available, hence why I didn't ask the professors directly. I'll give some thought to your hints, and I thank you for answering, but I'd also love a straight answer if I end up not reaching one :) Jan 24 at 19:06
• If by E* you mean the language of all strings which can be formed by concatenating symbols from the language, we only need one state (initial state = acceptance state), which is never left. And I guess it is hard to test whether a given TM accepts E* (cs.stackexchange.com/q/60502/96482), so this would be a counter example and we could say that it is undecidable. Jan 26 at 10:12
• @d-w Could you please confirm that the reasoning is sound? Jan 29 at 17:18

The language is undecidable, and is proven immediately by Rice's Theorem.

These languages are recursively enumerable (since they are the languages of Turing machines), and being accepted by a Turing Machine of at most 37 states is a property of those languages; furthermore some languages will fit the criteria (being accepted by a Turing Machine of at most 37 states) while others won't, so it is a non-trivial property. Hence, by Rice's Theorem it is an undecidable property.