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

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ What is T(M)? Is it the language generated from the turing machine M? $\endgroup$
    – nir shahar
    May 28, 2020 at 14:23

1 Answer 1

Reset to default
-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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Rice's theorem does not apply here. $\endgroup$
    – cody
    Jun 28, 2020 at 3:39
  • $\begingroup$ Why? The conditions to it are obviously met $\endgroup$
    – nir shahar
    Jun 28, 2020 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.