===========================================================================
CSC 363H               Exercise 2 -- Grading Scheme               Fall 2007
===========================================================================

As usual, take off marks for ambiguous or incorrect notation, ambiguous or
vague or incorrect claims that are not substantiated, or any other aspect
of the answer's write-up that makes it difficult or impossible to
understand.

A.  [5 marks]

    1 mark: argument given in both directions and at formal level
    1 mark: correct ideas (for both directions)
    3 marks: correct details of equivalence

B.  [7 marks]

    1 mark: attempt to prove both directions, at the right level
    3 marks: correct proof of recognizability of L_f
    3 marks: correct proof of computability of f

-----------------
Marker's Comments
-----------------

A.  Mostly done pretty well.  Common mistakes:
    1.  A few gave an example instead of a formal proof.
    2.  Some students introduced only one new state.
    3.  For some new state q, students forgot to define d(q,x) for all x in
        the tape alphabet -- instead they defined it only for the x that
        the head was reading in the previous configuration.
    4.  Some students believed that "stay put" is a state.

B.  Only a few did well.  Common mistakes:
    1.  Students believe that for the decider L_f, the input looks like
        w#f(w), and they treat the part after # just like being f(w).
    2.  Most of them seem not to know even the definitions.  It is hard to
        describe a common mistake here, since many answers appeared to be
        more or less random sentences.

Apart from these comment, a common mistake in both questions is that
students find it hard to understand the concept of the existence of a TM.
That is, they do not understand that in order to prove a statement, they
have to assume the existence of a TM M (enjoying some properties), and
using M (as a subroutine) to built a new TM M' (that meets some other
properties).  In particular they are confused about what kind of input each
TM should have.