Q3:  Show L RE -- 5 marks
     Show L not recursive -- 5 marks

Most students only did one half of this problem (generally showing
that L was not recursive with a reduction from L_U.  Note that
reducing L_U to L only shows that L is not recursive, not that it is
RE.  The best way to show a language is RE is to actually present an
algorithm/Turing Machine that recognizes that language.

Q4: Define PCP---3 marks
    Show L_U > MPCP > PCP -- 7 marks

Almost all students defined PCP correctly, but most failed to
correctly outline a reduction from L_U to PCP.

Note that to get full marks, students should have described briefly
the way in which an instance of MPCP was constructed to simulate the
computation of M on w (i.e. that the strings in A and B are chosen by
looking at M's transition function). (I took off two marks for this)

Q5:  Given an instance <A,B> of PCP:
     Construct an appropriate grammar G  -- 4 marks
     Show that G ambiguous iff <A,B> is in PCP -- 6 marks.

This was generally done very poorly.  Many students got part marks
(1-3) for showing some insight into a reduction from PCP > ambiguity.