1
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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^*$?

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 :) $\endgroup$
    – user2891462
    Commented Jan 24, 2023 at 19:06
  • $\begingroup$ 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. $\endgroup$
    – user2891462
    Commented Jan 26, 2023 at 10:12
  • $\begingroup$ @d-w Could you please confirm that the reasoning is sound? $\endgroup$
    – user2891462
    Commented Jan 29, 2023 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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