Test 1 notes from the marker:

Question 1:

1. You can't choose the number of heads in the multiheaded T.M. When it 
comes to TMs you can certainly do so because of the theorem given in 
your text.

2. In this question we don't "simulate" by giving a TM that runs on 
<M,w>. In this course the term "simulation" takes two different 
meanings. One is emulation of a TM within another TM and the other is 
when we simulate using a universal TM. Please clarify any confusion for 
future reference.

To give full marks for this question I was expecting to see at least a 
statement that mentions how to construct the transition function. I did 
not subtract any marks if you didn't have a proof (i.e. the "argument on 
the computation" - seeassignment 1 solutions & remarks).

Question 2:

Again students messed things up with enumerators. Please check the 
related remark on assignment 1 remarks.  Clearly, since the same 
mistakes were done in assignment 1, and the situation was explained 
thoroughly in the "marker's remarks" zero marks were awarded for similar 
"solutions" in the exam.

The same remark as in the remarks for assignment 1 holds here too when 
it comes to enumeration of strings which contain 0. YOU CANNOT ASSUME 
THAT YOU HAVE SOMETHING NOT GIVEN IN THE HYPOTHESIS OR THAT YOU CANNOT 
ASSERT ITS EXISTENCE. You cannot say I'll use an enumerator for Sigma*, 
unless you say why it exists. In the same sense you cannot say I will 
use the TM that solves the question!


Question 3:

Most people argued relying on the fact that A_TM is undecidable. In your 
construction it's a very bad idea to reject every input string that  is 
not equal to w. What happens when M(w) accepts and w does not contain 0?


All questions: of course there were solutions that make no sense mixing 
up terminology and notions in a strange way, "directions" inside proofs 
(e.g. reduce L to A_TM instead of the opposite) etc. Most of these 
received from 0-3 marks depending on content.