1
$\begingroup$

Is it possible to use the theorem of Rice to prove that the emptiness problem is undecidable?

With the emptiness problem I mean the question if a certain machine doens't accept any input ?

If you can prove it using the theorem of Rice, can you also prove the acceptance problem (if a certain machine will accept a certain string?).

$\endgroup$
  • 2
    $\begingroup$ What do you think? Have you tried proving these statements using Rice's theorem? Where did you get stuck? $\endgroup$ – Yuval Filmus Jan 22 '17 at 17:22
  • $\begingroup$ I think that you can prove them both using Rice, since they are both non-trivial and language invariant. But the theorem of Rice is proved bij the fact the you can't decide the acceptence problem, so it looks a little bit weird if you use the theorem of rice to to prove that the acceptance problem is undecidable. $\endgroup$ – Pieter-Jan Coenen Jan 22 '17 at 19:03
  • $\begingroup$ Deducing undecidability of the halting problem (what you call the acceptance problem) from Rice's theorem shows that Rice's theorem generalizes the undecidability of the halting problem. The fact that you might use the latter to prove the former doesn't make any difference. If, however, you are giving a formal treatment of computability, you should avoid such circular references in proofs. $\endgroup$ – Yuval Filmus Jan 22 '17 at 22:05
  • $\begingroup$ I vote to close since you seem to already know the answer. $\endgroup$ – Yuval Filmus Jan 22 '17 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.