1
$\begingroup$

I would like to determine if the following language is decidable or not. L = { w $\in$ $\Sigma^*$ | $T(M_w)$ is recognized by a Turing machine with at most 42 states}.

I know that every finite language is decidable, but I am not sure if this has anything to do with this particular problem.

Every help is appreciated, I am a little lost.

Thank you

$\endgroup$
1
  • 2
    $\begingroup$ What is T(M)? Is it the language generated from the turing machine M? $\endgroup$ – nir shahar May 28 '20 at 14:23
-1
$\begingroup$

Define C = { $L | L$ is decidable by a turing machine with at most 42 states }

Notice that there is a finite amount of such languages, as there are a finite amount of turing machines with 42 states. for that reason, we have $C\ne\emptyset, \sum^*$

By Rice's theorem, the language $S=$ { $w | L(M_w) \in C$ } is undecidable. This language is precisely the language in question

$\endgroup$
2
  • $\begingroup$ Rice's theorem does not apply here. $\endgroup$ – cody Jun 28 '20 at 3:39
  • $\begingroup$ Why? The conditions to it are obviously met $\endgroup$ – nir shahar Jun 28 '20 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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