===========================================================================
CSC 363H              Tutorial Exercises for Week  5            Summer 2006
===========================================================================

 -  Show that it is undecidable to determine whether or not a TM M halts
    when started on a blank input tape.

 -  Show that A_TM <=m (E_TM)^C (the complement of E_TM) but
    A_TM does not <=m E_TM.

 -  In general, how can you show that a language A does not reduce to a
    language B?

 -  Show that if A is recognizable and A <=m A^C, then A is decidable.