===========================================================================
CSC 363            Homework Exercise 2 -- Marking Scheme          Fall 2008
===========================================================================


NOTE TO STUDENTS:

You will find below the marking scheme used for your homework, including
the meaning of marking codes and number of marks associated with each one.
This file also contains my instructions to the marker (so you can get an
idea of how the homework was marked) and the marker's comments about each
question.

Please take the time to read this carefully before you ask questions about
the grading of your homework.


NOTE TO MARKER:

Be picky!  On any homework, it is the responsibility of students to show
that they understand how to solve each problem and to write up their
answers carefully.  At the same time, keep in mind that exercises are worth
only 1.5% of the final grade, so your marking should be somewhat coarse.
And remember that marking is not just about evaluating the students's
performances, but also about giving them feedback so that they can learn
from their mistakes.  This is especially important for students who made
numerous or more serious mistakes, as they are likely to need more feedback
in order to understand why their answers were incorrect.

For each question, I list solution elements with an associated code for
writing on student papers (the letter(s) between underscores _) and a
number of marks.  There are also general errors (with associated codes)
given below, with a maximum number of marks to take off for each type of
general error (as a percentage of the value of the question).  You will
likely encounter other common errors, or maybe decide to break down the
marking scheme further.  Simply make note of these changes/additions to
the marking scheme, and introduce new code letters (or short words) to
allow you to quickly give accurate feedback to the students (both in terms
of what they did wrong and how many marks it cost them).


GENERAL ERRORS (marked negatively, in addition to any other errors):

    _N_otation [up to 20%]:  incorrect/ambiguous notation

    _V_agueness [up to 20%]:  incorrect/unjustified/vague claim


1.  [15 marks]

    _S_tructure [3 marks]:  clear attempt to describe how to simulate TMs
        with ITMs and how to simulate ITMs with TMs, including formal-level
        descriptions

    _I_dea [6 marks]:  correct ideas for each simulation (as evidenced by
        comments), and reasonable explanation of each simulation's
        correctness, including correct way to simulate acceptance/rejection
        at the right time

    _D_etails [6 marks]:  correct formalization of the ideas

    Marker's Comments -- Additional Error Codes:

    ITM -> TM

    I1: Requires special symbol at leftmost square.  ITMs reject when
        moving left off left-end.  TM must simulate this by failing when
        moving left on the left-most square.  Can't know that head is on
        left-most square without special character.  Can't reject when head
        moves left onto a space, eg, could move past w on the tape, move
        left and see a space.  Shouldn't reject in that situation.

    I2: ITMs begin in the configuration "q_0 _w".  For a TM to compute from
        the same configuration, the _ to the left of w must be inserted.

    D1: Need to add states to shift w to the right.  Requires at least 1 state
        for each symbol in \Sigma.
        * See online lecture notes for example on shifting w to the right.

    D2: ITMs don't have states q_A and q_R.  TMs require these states.  When
        defining Q for your TM, must add states q_A and q_R to the states
        from the ITM.

    D3: Need to specify that # !(- \Gamma.

    TM -> ITM

    I4: Requires special symbol at leftmost square.  TMs can "bounce" off
        the left edge.  Without a special symbol to alert the ITM that it
        is on the left-most square, the ITM will move left off the left edge
        and reject.

    D4: Requires a special state to "reject".  Should enter this state whenever
        TM would enter q_R.  This state should leave all input as is [not
        strictly necessary] and move to the left.  It will eventually move
        off the left edge and the ITM will reject as the TM did.
        \delta(q_move-left, a) = (q_move-left, a, L)  \-/ a (- \Gamma

    D5: TMs start in configuration "q_0 w".  When ITM begins immitating the
        TMs computation, it should also be in configuration "q_0 w".  Since
        the ITM begins with a leading _, need only to write the special
        symbol over the space, and then the ITM is in configuration
        "# q_i w".  Don't need to shift w over, otherwise the space will be
        reinserted, and the ITM won't have the same tape content as the TM.

    D6: Need to specify that # !(- \Gamma