1
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Jan 26, 2014 at 15:51
  • $\begingroup$ Rice's theorem considering non-trivial properties. $\endgroup$
    – TheNotMe
    Jan 26, 2014 at 17:52

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ So, overall, we can't use Rice for the problem I described, yes? $\endgroup$
    – TheNotMe
    Jan 26, 2014 at 17:17
  • 1
    $\begingroup$ On the contrary, I was trying to demonstrate that while Rice's theorem can be used, your own approach fails. $\endgroup$ Jan 26, 2014 at 17:29
  • $\begingroup$ You made me understand why my proof is wrong. But doesn't that also say that I am also wrong by applying Rice's theory? $\endgroup$
    – TheNotMe
    Jan 26, 2014 at 17:34
  • $\begingroup$ No, you're just applying the theorem in the wrong way. I suggest you have a look at the proof that the language of total Turing machines is undecidable. It addresses the part that bothers you. $\endgroup$ Jan 26, 2014 at 19:33
  • $\begingroup$ Which one are you referring to? The ones I reached do a proof by reduction. $\endgroup$
    – TheNotMe
    Jan 26, 2014 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.