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.