Proving that context-freeness of $L(M)$ is not semi-decidable using Rice's theorem This is a question from an exam I did today:


  Given $M$, a turing machine, we need to decide the following:
  
  1) $M$ halts on every input
  
  2) The language of $M$ is CFL


My question is, can I prove that this problem is not in $RE$ (recursively enumerable) using Rice's theorem? I understand that Rice's theorem works for languages and not machines, and when first looking at it, number 1 is a property of a machine not the language. But what I said, is that actually it is a property of a language: $M$ halts on every input iff $L(M)$ is decidable! (in $R$), so we can use Rice.

What do you think?
First of all, it is not true that $M$ halts on every input iff $L(M)$ is decidable. Indeed, $L(M)$ can be decidable even if $M$ doesn't halt on every input. Consider for example the machine which never halts on any input&mdash;the empty language is certainly decidable.

Rice's theorem considers properties of partial functions. The partial function is the one computed by the Turing machine, with $\bot$ representing the case that the Turing machine doesn't halt on a specific input. If a machine $M$ always halts then the corresponding function is total&mdash;never attains the value $\bot$. This is a property of partial functions, and fits within the framework of Rice's theorem.

If you're not sure about this, have a look at the proof that the language of total Turing machines (ones that halt on all inputs) is not decidable.