I have just began with my course of complexity and computability and I need your experience to help me progress !!

Something is not clear for me:


It is asked to determine if L1 is decidable or not, below the language is an answer given by a student. And I'm not agree with it...

The Rice theorem is given as follow :

Rice Theorem

I don't get why L1 is decidable since, for me, it looks like the Rice theorem could be immediately applied.

Did I understood very badly or am I right ? In the first case, why ?

Thanks in advance for your help !


  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – dkaeae Apr 4 at 7:08

Rice's theorem only applies for nontrivial properties, which are properties which are not always true or not always false. Your property is trivial, since it's always true.

  • $\begingroup$ Thanks for your answer !! Is it trivial because L1 is actually equal to RE ? $\endgroup$ – Elia Dratwa Apr 4 at 0:25
  • $\begingroup$ The semantic property is trivial and so the language is recursive. $\endgroup$ – Yuval Filmus Apr 4 at 5:15
  • 1
    $\begingroup$ @EliaDratwa L1 can not be equal to RE: L1 is a language, RE is a set of languages. The issue here is that $L1 = \{\langle M\rangle\ |\ M \mbox{is a TM}\}$, so to decide L1 we only need to understand whether a word is a description of some TM, which is a simple "parsing" problem, so to speak. $\endgroup$ – chi Apr 4 at 14:25
  • $\begingroup$ Thanks a lot !! $\endgroup$ – Elia Dratwa Apr 6 at 14:31

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.