======================================================================
CSC 363H            Marking Notes for Assignment 1         Summer 2006
======================================================================


1. Not many students answered what the questions were asking. Apart from 
the first question the others were asking for proofs not descriptions of 
TMs. For example, the definition of Turing-recognizable languages 
requires the existence of a particular type of a TM. When you are asked 
to show that a language is recognizable then by just mentioning the 
description of a TM you haven't done much (actually almost nothing). You 
have to prove that this object (i.e. TM) enjoys the required properties. 
Think of a more general scenario. In general, when you are asked to 
prove existence of something you may prove such a thing by exhibiting a 
particular object. Note that there are also other (non-constructive) 
ways to prove existence (in CSC363 you won't see many non-constructive 
proofs). But the important thing is WHY this object proves existence of 
an object with particular properties. For example, say that I ask you to 
show that there exists a prime number between 100 and 110. If you tell 
me 101 this does not prove existence, unless you explain why 101 is a 
prime number. In exactly the same spirit we have TMs which are SYNTACTIC 
objects. COMPUTATIONS of the TM is what is of interest.

Although, in many cases there were no proofs or even attempts to prove 
something I gave at least 2/3 of the marks just for correct construction.

2. By definition an algorithm=TM is a CONSTANT object. It doesn't adjust 
its description according to what inputs it takes (intuitively, think of 
the analogous irrational scenario where a real-world computer changes 
its hardware its time you run something different). Also, note that the 
number of tapes, tracks etc. are part of this constant object. A TM 
cannot add/remove tracks or tapes ``on the fly'' (i.e. as a function of 
the input). I subtracted for this mistake at most 2 marks but it's a 
very important thing to realize.

3. In question 3 many papers are messing up the notion of enumerator, 
recognizer, reduction and language. For question 3, there are papers 
that mix up things in an incomprehensible way. There are all shorts of 
presented solutions that make absolutely no sense. For example, some 
papers claim that they will present an enumerator for the language. Then 
they assume (out of nothing) the existence of another enumerator. And at 
the end they do not enumerate the language. Note that an enumerator for 
strings <M,k> in the language MUST enumerate machines M together with k. 
You are NOT given a fixed machine. Unfortunately it's not the case that 
these papers just messed up with terminology (I mean misuse of the term 
"enumerator"). Then, in the description of the TM they use another 
enumerator (I guess this is just an enumerator of stings in Sigma^*) 
which they don't say what it enumerates. In which order it enumerates. 
In the description of the machine it $k$ is not there. Why the strings 
of length k are important. Some attempts to argue that the strings of 
length k are of some importance they miss the point that all strings of 
length k will appear after finitely many steps (clearly we can give 
examples where for particular enumerations of Sigma^* the machine never 
terminates). Of course, there are all shorts of variations of this 
arguments that at some point there are reductions introduced out of 
nothing and for no apparent reason. Anyways, there is a clean argument 
without enumerators which in addition they are totally misunderstood in 
these papers. Students have to work in clarifying these important points 
of confusion. Clearly, I gave zero marks to such answers.