Proving that context-freeness of $L(M)$ is not semi-decidable using Rice's theorem

Question

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?

Answer 1

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.

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.