# 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?

• What is "Rice theory"? Do you mean Rice's theorem? If so, which version? You may want to check out this, this and this question. – Raphael Jan 26 '14 at 15:51
• Rice's theorem considering non-trivial properties. – TheNotMe Jan 26 '14 at 17:52

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—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—never attains the value $\bot$. This is a property of partial functions, and fits within the framework of Rice's theorem.