===========================================================================
CSC 363H                        Exercise 4                        Fall 2007
===========================================================================

A.  Show that there are countably many lists of 5 natural numbers.
    (Hint: For part of the answer, consider the sum of the numbers.)

B.  Show that there are uncountably many irrational numbers.
    (Hint: Use appropriate results from class to conclude this.)

C.  Explain the differences (if any) between ~A_TM (the complement of
    A_TM) and A' = { <M,w> : M is a TM that does not accept input w }.
    (Hint: How do we show that two sets are the same/different?)