University of Sussex 28 April 2017
Feedback Limits of Computation Test – Dr Bernhard Reus
• 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, write the program-as-data representation of the WHILE- program on the left (variable numbers start at 0):
test read X {
Y:= cons X X;
while X {
[0, [
[:=,1,[cons,[var,0],[var0]]],
[while,[var,0],[
[:=,0,[tl,[var,0]]] ] write Y ],1]
Typical Mistakes
List brackets forgotten around main body and loop body. For inout/output variables we only need a number not var. Some students forgot commas to separate list elements. Some students forgot the var encoding for variables as expressions.
2. Write the list below as element in D using only nils and ⟨ . ⟩-operations (linearly) [[0],[1]] ⟨ ⟨ nil.nil ⟩.⟨ ⟨ ⟨ nil.nil ⟩.nil ⟩.nil ⟩ ⟩
Typical Mistakes
Giving the encoding of [0,1] or [[0],[0,0]] instead of the given one. Some issues with bracketing. Also several students used ⟨nil⟩ which does not make sense as ⟨ . ⟩ is a binary constructor of trees in D.
3. Complete: E cons E F σ = ⟨ E E σ.E F σ ⟩.
Typical Mistakes
Those mistakes include just writing ⟨ E.F ⟩ or writing cons E E σ E F σ. Some students wrote unidentifiable terms including updates of σ.
4. Complete our definition of the Halting Problem below: HALT={[p,d]∈D| p(d)↓}
Typical Mistakes
Many students were not able to answer this. It was ok to add that p must encode a program. It is also fine to write p (d) ̸= ⊥. Some students also quantified over all d which does not make sense as d is fixed (but I ignored this if the rest was ok). Quite a considerable number of students wrote some terms involving d, p, and ⊥ that did not really make sense. A smaller error was to forget the semantics brackets around p.
5. Complete the sentence: “For an L-program p, the term [p]L denotes the semantics of p which is a function of type L-data → L-data⊥ .”
X:= tl X } }]
Typical Mistakes
Some students wrote D instead of L-data, which is not correct since we are talking about a general language L here, not WHILE. Writing just L was of course also wrong. Some forgot of course the lifting ⊥. Some wrongly wrote that this denotes the encoding of a program.
6. Every acceptable (i.e. reasonably expressive in a certain sense) programming language automatically admits reflective programming. This is a consequence of
Kleene’s (second) Recursion Theorem.
Typical Mistakes
Just ‘Recursion Theorem’ was also accepted as fully correct. Some wrote S-m-n Theorem and some wrote Church-Turing thesis. Although it’s a bit of a long stretch those contribute somehow to the explanation so some marks were awarded for those answers too.
7. Complete the sentence: “ ‘Game of Life’ is a 2-dimensional cellular automaton with four rules for: underpopulation, starvation, overcrowding, and survival.”
Typical Mistakes
Writing terms that are similar to survival and starvation gave also lots of marks. Note that overpopulation and undercrowding do not count. One student wrote “homeosta- sis” for survival which I liked (reminded me of ‘The Big Bang Theory’) Some students wrongly wrote graph automaton or regular or finite-state automaton.
8. Complete: “To show that a problem A is decidable it suffices to show that A is effectively reducible to any decidable problem.”
Typical Mistakes
Students swapped the direction. Also some student swapped the direction and used an undecidable problem as second one (which amounts to showing that A is unde- cidable). Some marks were awarded to those wrong answers too. Some students used a second problem B but did not say it was decidable. Some just write problem somewhere.
9. Which of the following problems are decidable? Tick the ones that are.
√ TSP HALT Complement of HALT √ Matching Tiling √ Primes
Typical Mistakes
This has been done well but some students forgot to tick TSP, some forgot to tick Matching. And some wrongly ticked complement of HALT.
10. Which of the problems below can be shown to be undecidable (by Rice’s Theorem)? (a) A={d∈D|d=pandtimeWHILE(d)>|d| }
√
p
decidable
undecidable by Rice’s theorem undecidable by other reason
(b) A={d∈D|d=pandprunwithinputdisnotnil }
decidable √
undecidable by Rice’s theorem undecidable by other reason
Typical Mistakes
All kinds of wrong combinations have been ticked. Most students ticked for (b) that Rice’s theorem can be used to show it’s undecidable. However, the problem is not extensional. Why is that?
Well, the property of programs used here talks about the effect of applying the program to its own encoding, so we it refers to the semantics of the program and the (encoding of) the program itself. Therefore, the property depends on the semantics as well as on the encoding of the program and not entirely on the semantics! If you ticked undecidable due to Rice’s Theorem you lost, however, only one mark.
11. Complete the following judgements about WHILE expressions and statements (n is a natural number). No need to show your working unless outlined:
Ttl X = 1+1=2
X:=tlX⊢time {X:n}⇒1+2=3 whileX{X:=tlX}⊢time {X:4}⇒
Typical Mistakes
4 × (3+2) +2
times loop body is executed
Often the answers 1 and 2, resp, were given for the first two parts. In some cases some t appeared miraculously (??). Some students wrongly added n in the second question. For the third part, well, all kinds of errors have been made. Marking was overall (as elsewhere) generous. But if your results were not numbers, but things like stores then you did not get many marks of course.
12. Assume we have a WHILE-program p such that timeWHILE(d) = |d|3 + 5|d|2 + 2|d| + 8. p
Tick only the statements that are correct. p ∈ WHILEtime(f ) where f (n) = n3 + 456
p ∈ WHILElintime
√ p has a time bound in O(n5)
√ p has a time bound in O(n3) p∈PWHILE
√ f(n)=n3 +16n2 isatimeboundforp Often p ∈ PWHILE was ticked. Also often p has a time bound in O(n5) and f(n) =
n3 + 16n2 is a time bound for p were not ticked.
13. Complete: L1 ≼linear −pg −ind L2 means that (timed programming language) L2 simulates
L1 up to a program-independent linear (run-)time factor.
Typical Mistakes
This has not been done well overall. First of all L1 and L2 have sometimes been confused with problems or with programs (that run in linear time). It has been wrongly claimed that L1 reduces to L2 at times. Sometimes the simulation direction has been wrongly swapped. And the fact that the linear time slowdown is program independent needs to be mentioned, of course, for full marks.
14. Complete Cook’s thesis: “Computability up to polynomial time differences is equivalent for all (reasonable) for all sequential models of computation.”
Typical Mistakes
This was not as well remembered as I had expected. It’s ok to write P as answer for the first part. But “problems” without complexity specification loses some marks. Many students forgot the ’sequential’. The ’reasonable’ was optional – at least for marking purposes – here.
Typical Mistakes
15. True, false or unknown? Tick the boxes accordingly. √
TIMEWHILE(n) TIMEWHILE(n · log n) There are no problems that aren’t in NP 0-1 Knapsack is in P
WHILE ≼ptime TM
There is an A ∈ EXP such that A ∈/ P
Typical Mistakes
true false unknown true √ false unknown true false √ unknown √ true false unknown √ true false unknown
Difficult to spot trends here but some students that the first statement was wrong (it’s true by the Hierarchy Theorem). Some thought the first statement was false but it is actually unknown (since we don’t know whether P= NP). And quite a number of students also wrongly thought the fourth statement was false.
16. Complete: “Robustness” of P refers to the fact that decidability of problems in in polynomial time is independent of the (sequential) model of computation
(the decision procedure is written in).
Typical Mistakes
This is indeed Cook’s Thesis again, but rephrased somehow to explain the term robustness! It was ok to use ’in P’ as answer for the first part. Also the ‘sequential’ (although strictly speaking required) was not needed to get full marks. Note that you cannot ‘run a problem in a language’. When you write such a thing you always will lose some marks. Of course, all kinds of things synonymous with ‘model of computation’ were fully accepted as correct. Many got full marks and many got half marks.
17. Complete: “It is difficult to show that a problem is not in P. Currently, the closest to “TSP is not in P” that one can actually prove is “TSP is NP-complete ” under the assumption P̸= NP.
Typical Mistakes
This was the one question about NP-complete that I promised. Many students said “tsp is in NP” for the first part. You got marks for that, but of course this is not the closest to not being in P. For the second part many students wrote P ⊆ NP but that’s not an assumption, that’s a fact! You got marks for the assumption NP̸= P. If you assumed P = NP then obviously we’d already know that TSP is in P(as we know it is in NP). If you said that coherently you would get some marks but most students who used the assumption P = NP made then incosistent claims int he first part.