University of Sussex 25 April 2016
Limits of Computation Test
→→→→→→→→→→→ → → CandidateNo.
• Please answer ALL questions by writing on THIS SHEET. You are not
allowed to use any other documents or devices.
• Please write your candidate number in the box above.
• Questions are equally weighted (but Q1 – Q2 which have 2 extra marks each). Special “Spring” treat: your lowest scoring answer won’t count.
• You have 40 minutes to answer all 17 questions.
1. On the right hand side, complete the concrete WHILE-program that is represented as
data on the left:
[0,
[ [:=,[var,1],
[cons,[var,0],[quote,nil]]],
[while,[var,1],[]]
], 1]
Some test contained an alternative version:
[0,
[ [:=,[var,1],
[cons,[var,1],[quote,nil]]],
[while,[var,0],[]]
], 1]
prog read X {
Y := cons X nil ;
while Y {
}
} write Y
prog read X {
Y := cons Y nil ;
while X {
}
} write Y
Note: there was a (irrelevant) typo in the questions as the encoding of input and output variable are not [var,0] and [var,1], respectively, as they were on the test paper. this had no baring on the answers or results though.
Most typical mistakes Done really well. Some students forgot the semicolon after the assignment. A few students wrote quote explicitly in the program. And an as- sorted group of students had no clue apparently and wrote some fantasy expressions.
2. For each tree in D tick ‘yes’ if it represents a list of numbers and write the corre- sponding list – e.g. [2,3] – in the provided space, or tick ‘no’ otherwise.
⟨nil.nil⟩
⟨nil.⟨⟨nil.nil⟩.nil⟩⟩ ⟨⟨⟨nil.nil⟩.nil⟩.⟨⟨nil.nil⟩.nil⟩⟩ ⟨nil.⟨nil.⟨⟨⟨nil.nil⟩.nil⟩.⟨nil.nil⟩⟩⟩⟩
yes
yes
√yes[ 0 ]no √ yes[ 0, 1 ] no √ no √ no
Most typical mistakes Interestingly, the third option was relatively often inter- preted as [1,1]. Something I cannot understand really. More understandable, but equally wrong for the third option was [2,1] and [2,2]. Some students ticked yes for three and wrote things like [[1],[1]], which is clearly not a list of numbers.
3. Complete the sentence: “WHILE programs are a good choice for effective procedures because WHILE has just the right mix of simplicity and expressivity.”
[Neil Jones]
Most typical mistakes Done really well (I had mentioned it often enough, haven’t I?) Of course there were some random guesses like “computability and complexity” or “properties and syntax”, and all kinds of other things.
4. Complete the sentence: “The fact that we can compile TM programs to WHILE- programs and vice versa, and WHILE-programs to SRAM programs and vice versa,
is evidence for the Church-Turing thesis”.
Most typical mistakes Done extremely well. Only five students got it wrong. Two did not write anything and three unfortunately wrote “Cook’s thesis”, which cannot be accepted here as complexity has not been mentioned!
5. Complete the definition of the operational semantics of the given RAM assignment: p⊢(l,σ)→(l+1,σ[σ(i):=σ(j)]) ifIl =
Most typical mistakes Well, there were problems. A number of students had forgotten the indirect addressing requiting the extra σ on the left. Some students wrongly wrote instead an extra σ on the right. There were all kinds of strange things. I marked generously but no marks for fantasy notations.
6. Complete the sentence: “The problem whether any given L-program p terminates when run on any given input d is called the Halting Problem (for L). This problem is undecidable.”
Most typical mistakes This has been answered very well. A number of students lost one mark because they were not clear about what the input was to p. I was relatively generous with the interpretation of statements in that regard. Note that our definition of the Halting Problem does not refer to all input as a few wrote (only one mark penalty for this though). A number of students wrongly wrote “is defined” instead of “terminates”.
7. Complete: “To show that a problem A is undecidable it suffices to show that the Halting Problem [ any other undecidable problem accepted as correct] is effectively reducible to A.”
An alternative version used in the alternative version of the test was the inverse of this statement:
Complete: “To show that a problem A is decidable it suffices to show that A is effectively reducible to a decidable problem.”
Most typical mistakes Version 1 A large number of students swapped the the roles of A and the Halting Problem, so the reduction is in the wrong direction (in this case 2 marks were still awarded).
Most typical mistakes Version 2 A large number of students swapped the the roles of A and the decidable problem, so the reduction is in the wrong direction (in this case 2 marks were still awarded). Some students used the Halting Problem which is wrong on this case.
Some students wrongly used “L-data”. A few students wrongly tried to use the complement of A, but there is no reduction if one wants to apply the theorem that a set is decidable if it and its complement are both semi-decidable. So this does not fit at all.
8. Which of the following problems are undecidable? Tick the ones that are.
Postman Parsing √ Tiling √ Halting Graph Colouring Primes
(Note that some tests answers were presented in a different order.)
Most typical mistake Done well in general. Only very few students appeared to do some random guessing. Postman appeared a few times as undecidable, but of course it is in P.
9. Which of the problems below can be shown to be undecidable (by Rice’s Theorem)? (a) A={d∈D|d=pandtimeWHILE(a)≤1,200,000foralla∈D}
decidable √
undecidable by Rice’s theorem undecidable by other reason
(b) A={d∈D|d=pandpcompilesWHILEintoCM-programs} decidable
p
√ undecidable by Rice’s theorem undecidable by other reason
No typical mistakes here Answers are all across the board. While many have it
all right. Many have one or both wrong.
10. Complete the sentence: “ If E is a WHILE-expression, T E denotes the time
it takes to evaluate WHILE-expression E; for instance, T cons hd X nil evaluates to 1+1+1+1=4 .”
Note that 4 was enough as an answer but it helped (for wrong answers) if you gave the terms of the addition.
Most typical mistakes A few students have not said what time of E is measured (to evaluate), but just vaguely talked about “time cost”. Some students did not fully evaluate the given term and answered something like e.g. 1 + 1 + 1 + T X or something slightly less correct. A few people randomly guessed e.g. “Turing machine implementation” (??)
11. Complete the definition:
C;S⊢time σ⇒t+t′ if C⊢time σ⇒t, C⊢σ→σ′ andS⊢time σ′ ⇒t′.
Most typical mistakes This has not been answered that well (although a number of students got it right). A few students did not even attempt to answer this. A number of students did not use the right → notation for the operational semantics of C and also did not use stores σ → σ′ but sometimes used numbers, usually because they used wrongly ⊢time . Therefore also in the second part they often wrongly wrote S⊢time σ⇒torS⊢time σ⇒t′.
12. Define formally or informally (in any case precisely) the class LINL: It is the class of all problems over {0, 1}∗ that can be decided
by an L-program in linear time .
Most typical mistakes This has been answered reasonably well. But many stu- dents wrote that it is a class of programs, which it is not. Sloppiness caused all kind of wrong statements, e.g. “problem in (language) L” or “a language with . . . limits” or talked about “problems that run” (?) or “programs that run with language L” (alternatively they are apparently “executed” or “evaluated”), “decidable by lan- guage L”. Several students used the term “L-problem” which I have not introduced and they should have explained if they used it. I generously awarded 1 mark if the answer contained the word “linear”, even if the rest was completely wrong or even incomprehensible. Some students wrongly thought this to be a time bound, i.e. a function. A few students did not even attempt to answer.
13. True, false or unknown? Tick the boxes accordingly. The Postman problem is feasible
PGOTO = PTM
WHILE ≼lintime GOTO
There is an A ∈ EXP such that A ∈/ P
√ true false unknown √ true false unknown √ true false unknown √ true false unknown
Note that the order of answers was different in different versions of the test.
No typical mistakes Answers were all across the board. Quite a number of students though the Postman Problem was not feasible or unknown to be feasible. Of course we know it is in P but we also know that the polynomial of the runtime bound is of small degree so it is known to be “feasible”.
14. Fill in the gaps in the Linear Hierarchy Theorem: “There is a constant b such that for all a ≥ 1 there is a problem A in TIMEWH1LE(a×b×n) that is not in
in TIMEWH1LE(a × n).”
Most typical mistakes The second part has been answered better than the first. Typical wrong answers for the first part are “constant” or “b ≥. Typical mistakes for the second part are TIMEWH1LE(b × n) or TIMEWH1LE(a × b × n). A number of students did not attempt the question or wrote some random things.
15. Assume we have a WHILE-program p such that timeWHILE(d) = 12|d|3 + 3|d| + 4. p
Tick only the statements that are correct.
p ∈ TIMEWHILE(f) where f(n) = n3 + 10n + 10
p∈TIMEWHILE(O(n3 +n+6))
p ∈ TIMEWHILE(f) where f(n) = 9n2 + 512
p ∈ LINWHILE p∈PWHILE
p ∈ TIMEWHILE(O(n3))
Would have been the correct answer as all given classes are problem classes. But only one student had picked up on that. So I decided to mark all other answers that have awarded at least one tick as if the question was like this:
p ∈ WHILElintime √ p ∈ WHILEptime
√ p ∈ WHILEtime(O(n3))
given that all but one student seemed to have understood it that way. I did not
award penalties for that misunderstanding.
Note that in some test papers the answers were presented in a different order. No further typical mistakes Answers were across the board.
16. Tick what is known to be true about the Travelling Salesman Problem. It is … inP inLIN √inNP inOn×logn6 √inO(n!×2n)
√ decidable undecidable √ semi-decidable
Note that in some test papers the answers were presented in a different order.
Most typical mistakes Errors appeared across the board but probably the most common ones were to forget to tick “semidecidabe” (note that a decidable problem is automatically semidecidable) and O(n! × 2n) as this describes more time than one actually needs to look through all possible tours.
p ∈ WHILEtime(f) where f(n) = n3 + 10n + 10 √ p ∈ WHILEtime(O(n3+n+6))
p ∈ WHILEtime(f) where f(n) = 9n2 + 512
17. Let A ∈ NP and B ∈ NP. Is the concatenation of words from A and B, i.e. {w | w = st such that s ∈ A and t ∈ B}, also in NP? √ true false Reason: the certificate of the verifier contains s and t plus certificates fors∈Aandt∈B. Thenuseverifiersfors∈Aandt∈B.
Most typical mistakes Most students ticked “true” correctly (for one mark), but nobody gave a fully convincing high level answer. (Note that this question was intentionally difficult). Some students answered a different question about A ∪ B.