=========================================================================== CSC 363 Homework Assignment 2 -- Marking Scheme Fall 2008 =========================================================================== NOTE TO STUDENTS: You will find below the marking scheme used for your homework, including the meaning of marking codes and number of marks associated with each one. This file also contains my instructions to the marker (so you can get an idea of how the homework was marked) and the marker's comments about each question. Please take the time to read this carefully before you ask questions about the grading of your homework. NOTE TO MARKER: Be picky! On any homework, it is the responsibility of students to show that they understand how to solve each problem and to write up their answers carefully. Remember that marking is not just about evaluating the students's performances, but also about giving them feedback so that they can learn from their mistakes. This is especially important for students who made numerous or more serious mistakes, as they are likely to need more feedback in order to understand why their answers were incorrect. For each question, I list solution elements with an associated code for writing on student papers (the letter(s) between underscores _) and a number of marks. There are also general errors (with associated codes) given below, with a maximum number of marks to take off for each type of general error (as a percentage of the value of the question). You will likely encounter other common errors, or maybe decide to break down the marking scheme further. Simply make note of these changes/additions to the marking scheme, and introduce new code letters (or short words) to allow you to quickly give accurate feedback to the students (both in terms of what they did wrong and how many marks it cost them). GENERAL ERRORS (marked negatively, in addition to any other errors): _N_otation [up to 20%]: incorrect/ambiguous notation _V_agueness [up to 20%]: incorrect/unjustified/vague claim General Marker's Comment: A completely correct argument has two ingredients. First ingredient is the right idea. Second ingredient is the supporting argument that shows that the preceding idea (e.g., some construction) actually works as it is supposed to. This means that students that feel they wrote the correct idea but that marks were deducted, should ask whether they provided enough justification. 1. [18 marks] (a) [8 marks] _S_tructure [2 marks]: clear attempt to do a counting argument (countably many computable functions but uncountably many functions means some functions are uncomputable), or to exhibit a specific uncomputable function and prove that it cannot be computed (most likely by contradiction) Counting argument: _D_iagonalization [4 marks]: correct argument there are uncountably many functions -- either through direct diagonalization, or through correspondence with another uncountable set _C_onclusion [2 marks]: correct argument there are countably many computable functions, and conclusion Specific example: _F_unction [2 marks]: correct example of uncomputable function _P_roof [4 marks]: good argument that function is uncomputable, including structure of argument (even if function is in fact computable) (b) [5 marks] _S_tructure [1 mark]: clear attempt to diagonalize to show uncountable, or to give explicit list of all elements and argue the list contains each element exactly once _D_iagonalization [4 marks]: correct diagonalization argument (or correspondence with another uncountable set) (c) [5 marks] _S_tructure [1 marks]: clear attempt to diagonalize to show uncountable, or to give explicit list of all elements and argue the list contains each element exactly once _L_ist [4 marks]: correct way of listing all pairs of strings, and reasonable justification that the list is correct Marker's Comments/Error Codes: Aa1 [-1 mark]: enumeration of all strings missing. Aa2 [-1 mark]: should be explicit that every computable function f : \Sigma* -> \Sigma* is computed by some TM (by definition), and each TM computes at most one function -- not enough justification Ab3: Suppose you want to show that A is uncountable, given that you already know that some B is uncountable. A 1-1 mapping from A to B does not prove anything. On the contrary, for every countable set A there exist a 1-1 mapping to an uncountable set B. What is impossible, is to engineer an *onto* mapping. 2. [30 marks] _S_tructure [2 marks for each part]: clear attempt to describe explicit recognizer and argue its correctness, or to perform specific mapping reduction from an unrecognizable language, including correct structure of reductions A <=m B (transform arbitrary inputs x for A into specific inputs y for B, argue transformation is computable and x (- A iff y (- B) (a) [8 marks] _C_o-recognizable [3 marks]: correct recognizer for ~L_1 _U_ndecidable [3 marks]: correct reduction to show L_1 undecidable (b) [8 marks] _U_nrecognizable [3 marks]: correct reduction to show L_2 unrecognizable _C_o-unrecognizable [3 marks]: correct reduction to show L_2 co-unrecognizable (c) [8 marks] _U_nrecognizable [3 marks]: correct reduction to show L_3 unrecognizable _C_o-unrecognizable [3 marks]: correct reduction to show L_3 co-unrecognizable (d) [6 marks] _U_nrecognizable [2 marks]: correct reduction to show L_4 unrecognizable _C_o-unrecognizable [2 marks]: correct reduction to show L_4 co-unrecognizable Marker's Comments/Error Codes: Breakdown of marks: In each subquestion you need to show two things. For each of them, 1 point for structure, 1.5 points for correct idea (e.g., construction of a TM) and 1.5 points for correct justification (except from d that takes 1 point each for structure, correct idea and correct justification). For proving a weaker statement, students get 1/2 the marks (2 instead of 4). Ba1: the negation of the sentence "TM M accepts string w" is "TM M does not accept string w" or alternatively "TM M either rejects or loops on input w" Ba2: A TM that performs a <=m reduction needs to always halt. For example, such a machine cannot check whether some other TM accepts some string. Bd3 [-3 marks]: Suppose that A, B are languages unrecognizable and co-unrecognizable respectively. Can we say the same thing about their union? The answer is no. Here is an example: define L = EQ_TM u ~EQ_TM; then L is decidable. 3. [32 marks] (a) [8 marks] _S_tructure [2 marks]: clear attempt to prove both directions, with good structure in both directions (in particular, correct use of assumptions) _E_numerator [3 marks]: correct enumerator for decidable languages _D_ecider [3 marks]: correct decider for languages that can be enumerated in lexicographic order Breakdown of marks: For each direction, 1 mark for structure, 1.5 for correct idea (e.g., correct decider) and 1.5 for sufficient justification. (b) [8 marks] _S_tructure [2 marks]: clear attempt to describe a specific decidable language and prove it is an infinite subset of recognizable language L (including correct use of assumption L is recognizable) _L_anguage [2 marks]: correct decidable language L' _A_rgument [4 marks]: good argument L' is an infinite decidable subset of L -- also corresponds to a correct enumerator, depending on what students chose to write Marker's Comments/Error Codes: Ca1 [-1 mark]: It is important to distinguish between finite and infinite languages. To see why consult the sample solutions, and observe why it is important for the language to be infinite so that the enumerator yields the correct decider. (c) [8 marks] _S_tructure [2 marks]: clear attempt to consider all possibilities and either give a specific example or a general argument that it is impossible, based on known properties of <=m _D_ecidable [2 marks]: correct example for decidable languages _R_ecognizable [2 marks]: correct argument for languages that are recognizable (or co-recognizable) but undecidable _U_nrecognizable [2 marks]: correct example for unrecognizable and co-unrecognizable languages Marker's Comments/Error Codes: Cc2: The difficulty with this question is to convince us that there are examples that cover each case. Therefore it is not enough to just say that some cases are possible (which only gets 0.5 points for each case). Omitting this also deducts marks from structure -- usually -1. (d) [8 marks] _S_tructure [2 marks]: clear attempt to describe specific decidable language C and prove it separates A and B (including correct use of definition of "separates") _L_anguage [3 marks]: correct decidable language C _A_rgumant [3 marks]: good argument that C separates A and B