===========================================================================
CSC 363H                  Tutorial Exercises # 6                  Spring 2007
===========================================================================

 -  Exercise 5.7, p211. Rather than reading the solution, try solving it yourself.

 -  For every language L, define E_L = { <M> : M is a TM and L(M)=L }.
   Show that: for every L, E_L <=m EQ_TM.

   Hint. Consider separately the cases: a) L is recognizable and
   b) L is not recognizable.

 -  Let DECIDER_TM = { <M> : M is a TM and M is a decider }.
   Show that neither DECIDER_TM nor its complement are recognizable.