Marker's comments for the midterm test (Steve)

Overall this test was pretty easy and students did well: 
(average mark was 32/38).

Question 1:   Several students drew a matrix with the rows
labelled something like By1, By2,... and columns labelled
something like x1, x2, ..., and then indicated that the diagonal
elements were flipped.   This is OK, but it is important to
explain that both x1, x2, ...  and y1, y2, ... are enumerations
of Sigma^* in lexicographical order (so in fact xi = yi).

-2 for not explaining this
-2 for not explaining that C is decidable.

NOTE:  The version of this test posted on the web differs slightly
in Question 1 from the original, in that the phrase
`using a diagonal argument' is omitted.  Of course the intention
is that students should use a diagonal argument, but students
shouldn't have to be reminded.

Question 2:  Students did well (too easy).

Question 3:  This was the most interesting question.
Most students did well.   The most common mistake was to assert
that \overline{A} is semi-decidable, claiming that a certificate
is a pair of accepting computations of M, accepting two different
strings.   The trouble with this is that M might not accept any
string at all, and still be in \overline{A}.  There is no certificate
for this (and in fact \overline{A} is not semi-decidable).