Test 1 expected answers:

These outline the expected answers. There may be other correct answers,
or other answers which can score significant points.

1. L(M) = { strings starting and ending with 0 }
   M halts on all strings.

2. Similar to the quiz and the proofs from the notes, class and tutorial.

3. Answers will vary. The output string should look like
	#1#11#111#1111#....
   Equivalent outputs are accepted.

4. This reduction is nearly identical to the reduction solving
   question 10 on the homework.

5. The complement of this language is almost DIAG.



Test 1 grading scheme:

1. 2 points for correctly identifying the language
   5 points for proving the language correct
      common problems:
	- only showing base cases
	- poor induction on length of string
	- induction on "M accepts |x| = k"
	- invalid or inapplicable induction hypothesis
   3 points for proving it is decided.
	- just stating it halts on all input, no argument = 1
	- don't know = 1

2. 5 points for each direction of the equivalence.
	- Stay equiv to L then R moves = 2
	- Stay = L,R with markers, not explicit how to do stay = 3
	- proving multitape, not multihead = -2 of mark

3. 5 points for the enumerator:
	1 point for gamma = {1,#,blank} or equivalent
	1 point for Q finite
	3 points for delta complete and mostly correct
	-.5 for using epsilon as tape symbol, rounded
   5 points for correctness argument and comments.
      common problems:
	- not clear about what the machine does
	- argument doesn't match machine action
	- not presenting delta, just saying how machine would work = 5 max

4. 10 points for proving the reduction:
   10 = mostly correct, perhaps missing minor details
   8 = somewhat correct, missing a major detail
   6 = right idea, can be extended to a correct proof adding details
   4 = incorrect proof, but right approach, shows insight to problem
   2 = wrong, but at least knows what a reduction is and how to approach
   0 = completely wrong, no indication of understanding reductions

5. 10 points for the proof. Highly successful methods included
   contradiction, reduction, and considering the complement language.
   10 = mostly correct
   8 = somewhat correct, missing significant details
   6 = right idea that can be easily extended to a correct proof
   4 = incorrect, but using the right approach, shows insight
   2 = wrong, but knows how such a fact could be proven
   0 = completely wrong, i.e., "proved" decidable

Generally, a large proportion of incorrect answers could have more
been answered "I don't know" to earn the same or more marks.

Overall, the Turing machine questions were fairly well done.
But the decidability questions were generally poorly done, with some
notable exceptions.

What does your mark mean?
   - mid 30's and higher is quite good, be proud
   - high 20's-low 30's good, but can be improved
   - low 20's about average, put in some more work to improve
   - 17-18 is borderline passing
   - low teens and single digits: look for help immediately (come to
   office hours, read through the material again, work on problems)
Remember this is only one third of the course, and probably the hardest
part of the class to understand!