=========================================================================== CSC 363H Exercise 3 -- 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. [4 marks] 1 mark: correct argument f computable -> L_f recognizable 1 mark: use or mention of dovetailing in second argument 2 marks: correct application of dovetailing; details of arguments B. [4 marks] 1 mark: correct argument for intersection 1 mark: correct main idea for concatenation 2 marks: correct details for concatenation (at most 1/2 for correctly describing an incorrect idea) C. [4 marks] 1 mark: correct argument for union 1 mark: correct main idea for concatenation, use of dovetailing 2 marks: correct details for concatenation (at most 1/2 for correctly describing an incorrect idea) ----------------- Marker's Comments ----------------- General comments: 1. Most arguments were incomplete. In particular, when we have to prove that a language is recognizable, then a description of a Turing Machine is not enough. One has to argue that the TM meets exactly the properties it was supposed to (proof of correctness). Otherwise, presenting a TM for a recognizing language is more a claim that the language is recognizable rather than a formal proof. 2. If a TM M is a recognizer, and you use it as a subroutine in the description of another TM, is not enough to argue only cases that M accepts or rejects. M as a recognizer might loop for ever, something we cannot predict. Moreover we cannot have conditions such as "if M loops" once again because we cannot check it (here loops means runs for ever). 3. Many students have not read the definitions, and they try unsuccessfully to solve the exercises. Worse, many students do not even read the questions carefully. So instead of arguing about recognizable languages, they keep using decidable languages (or they have not read the definition of computable function as stated in this exercise). 4. The Church-Turing thesis is some of the most important things mentioned this far in class. It somehow allows us to give high level description of TM, without having to give low level details, like what the head does, or what new special symbols we have to use. This is important, because now that we are convinced that we can have a TM for any algorithm we can think of, we can describe complicated TM without describing (for example) its transition function (this would be already terrible even for easily decidable languages). 5. When you design a TM it should be described on general (arbitrary) inputs. For example if you want to decide the language { x#y : x is in L and y is in L'} you are not allowed to assume that the input is given in the form a#b. In particular, you cannot describe the behaviour of a TM given the fact that the input is x#y where x is in L and y is L' (because if we were able to know this why would we need to design a TM?). In other words, the point of the TM is to figure out if the input has the form x#y with x in L and y in L'. In general, a TM should be described as if you did not know what the input would be. A. 1. Many students used dovetailing without mentioning it. Of course this is not a mistake, but it is useful when you are using a basic technique, to give the analogous credits. 2. Many students have not understood what the technique "dovetailing" does. More precisely, many students tried to apply some hybrid algorithms (dovetailing mixed with ideas from the previous assignment). Again, more importantly, their resulting algorithms are not correct. I believe that they do not understand the importance of dovetailing, and the problem we actually overcome by using this technique. I urge them to understand it deeply. 3. f is a partial function, and we cannot use if-statement of the form "if f(w) is defined", simply because we do not know whether f(w) is defined or not. For this purpose we have a TM (call it M), which we feed with w, and if f(w) is defined it will output an answer sooner or later. On the other hand if f(w) is not defined (and according to the definition), M might run forever, something we cannot predict. Think of M as a black box to which we sent questions from time to time, and we are expecting answers. We do not know how this black box works, and moreover we cannot stop it before it outputs an answer, simply because it might be the case that it needed 1 more second of calculations to do so. 4. Some students did the following mistake while "applying dovetailing"; they had an enumeration of S*={w_1,w_2,...}, but whenever they were checking (let's say) w_j for k many steps, they were not checking it again (in the future) for more steps. This way they were ruling out the possibility that the Turing machine needed just one more computational step to give an answer. 5. Some students did not use dovetailing but instead used enumerators to show that f is computable using that M_f is recognizable. This is a very nice idea. However, I would advise them to make sure that they know how to apply dovetailing as well, and moreover to understand its importance. B. 1. If we have some input, and we want to simulate some TM M on that input, it is wise to use a copy of the input. The reason for this is that we do not know how M behaves when running; for example M could overwrite the input making it impossible to simulate once again some TM on the same input. 2. Any TM needs to have a fixed number of tapes, and should be designed to run for inputs of any size. In other words when we are asked to design a TM, we are not allowed to have n working tapes where n is the size of the input. The reason is that once you fix the number of tapes (say) to k (and you do so since the description of the TM cannot depend on the size of the input), then you can only run your TM on inputs of size at most k (and therefore you do not actually solve the problem). C. Same as for B.