*********************
A6 Marking Scheme
*********************
******************
Q1. James + Roland
******************
a) -10 Claimed assertion was true.
-3 Small mistake in counter example
-5 Mistake in counter example, but had the right idea
-7 Provided an incorrect counter example
-5 Provided a heuristic explanation which demonstrated understanding of the problem, but no counter example provided
-7 Provided a weak explanation which demonstrated at least some understanding, but no counter example provided
-2 Argued that the union would be CE.
-1 Negligible Mistakes
b) -10 Claimed assertion was false
-5 Did not explain how to use the infinite semi-deciders such that we are ensured to halt on an accepted word (i.e. dovetailing the computation, iterating through them is not sufficient)
-7 Argued that CE being closed over finite union implies CE being closed over infinite union. (If this worked, the same argument could be used for a))
For both questions providing an answer without explanation or with a tautological explanation was given 0.
*************
Q2. Florestan
*************
Despite a first, more elaborate grading scheme, I ended up grading with an almost binary scale. This is because I was expecting to mostly read reductions, laid out in different shades of awkward/clean. Instead, an alarming number of you chose to argue with (false) closure properties. I think this question was very important to gauge your grasp of reduction/computability, so I really encourage you to read my breakdown of the common mistakes carefully and to review the examples of reductions you have seen so far.
For the grading scheme itself:
I was very harsh if you tried to argue with an argument relying solely on closure properties and did not give points if this was your only argument
I was however very generous if you gave any indication that you knew how to write a reduction argument (I generally gave full marks, even if the write up was a bit awkward).
More importantly, here is a list of the common mistakes that you should make sure to understand:
1. "Computable languages are closed under finite union therefore if a union of two languages is not computable, one factor at least must be non computable in the union"
-> "Computable languages are closed under finite union". This is true. But that does not imply the second part of the statement! It is definitely not true that, for a finite union to be computable, each set of the union must be computable. The first obvious counterexample is a non computable language and its complement, which obviously union to Sigma* and is thus regular. But no, despite what some of you tried to argue, this is certainy not the only counter example!
-> This is the same as the distinction/fallacy you've seen for the pumping lemma. Regular languages satify the pumping lemma, yes, but that does not mean that non regular languages cannot satisfy it. The equivalent here is that computable languages are closed under finite union, but nothing in this statement says anything about the closure properties of non computable languages, it could very well be that two non computable languages union to a computable one, just like a non regular language could very well satisfy still the pumping lemma.
2. "A is inside B and A is non computable so B is non computable"
-> This is clearly false: take Sigma* or any other big infinite computable languages that has a non-computable sub-language
3. "Let M be a Turing machine for K, this Turing machine has to use the Turing machine for L and/or L^c, which is a contradiction because there does not exist one".
-> An argument like this is not sound, because you cannot authoritatively declare what a Turing machine for K should or should not do. For example, the Turing machine for (E) U (E^c), where E is some non computable language, definitely does not need to use a Turing machine for E and/or E^c! There is something specific about the language K that does indeed force you to deal with L and L^c, but this is where the key lies and this is the core of the reduction. *And no, this is not about disjointness of the union!* (A non computable language and its complement are also disjoint.)
-> This is why a reduction works *the other way around*: you have no way of knowing how a Turing machine for M might work, it could be incredibly clever and do something no one thought of yet! (If you need evidence of this, look at the constant stream of unexpectedly clever algorithms that show known NP problems are in P). Because of this, a reduction goes the other way around: "Suppose M is a Turing machine deciding membership in K, I will show how to use that Turing machine to create a Turing machine that decides membership L" (as opposed to showing how the TM for K would necessarily use the TM for L, which is much harder to prove in general/virtually impossible).
4. "the word w does not halt" / "L does not halt"
-> It makes no sense for a word or language to halt/not halt. The *turing machine/algorithm* for L is what halts/does no halt (on a specific input w).
*************
Q3. Yue + Lin
*************
-claimed decidable without explanation: 5pts
-claimed decidable with explanation but chose the wrong way: 5-8pts
-claimed undecidable with explanation: 0 to 5pts depending on explanation **
-claimed undecidable with Rice's Theorem as explanation or gave no explanation: 0pts
-no mention of looping or repeating configs: deducted 5pts
-unclear about number of configs or number of iterations of the machine to find loop: deducted 1-3pts
-explicitly wrote out the number of configs (for 330 cells) got it slightly wrong: deducted 1pt
-small mistake(s)/vaguesness/etc: deducted 1pt
** many students gave a reduction to the halting problem and I gave 2pts for that
*******************
Q4. Molly + Johanna
*******************
a)
-1 for broad idea, not explicitly constructing DFA
-1 for using the transition function DELTA instead of DELTA* in construction
b)
-1 for handwavy argument in proof
-(2-3) for mistake in proof
-3 for missing part in proof (ex. a lot of people forgot to prove L is always context free)
-2 if state deciding if L(G) is regular reduces to checking if L(G) = SIGMA*, this is not what you just proved!
-5 for not stating that L(G) = SIGMA* is undecidable -> L regular is as well (why did we do the reduction)
Additional Comments:
-some people still don't know how the transition function works, or the difference between DELTA and DELTA*
******************
Q5. Prakash Panangaden
******************
I wanted to be sure that you told me how to search systematically through all possible 4-tuples of (x,y,dir,speed). One way is to encode this as a single positive integer then go through all of them one by one; most people with correct answers said this. I did not need detailed formulas or pictures, some people got full marks for a few clear sentences. Most people correctly explained how to find the present position from the guess. If you did not tell me how you were going to ensure you checked all possibilities I gave 10/20. A lot of people said, "somehow, go through all possibilities." Some people said the wrong thing: using a bounding box that increases does not work: I gave between 5 and 10 for this. Some people seemed to have no idea that the submaring was moving and just gave a way of zapping all the coordinates. For this you get 0. Very few people wrote completely wrong things.