University of Sussex 4 May 2018
Feedback Limits of Computation Test – Dr Bernhard Reus
→a→→→→→→→→→ → → 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, write the program-as-data representation of the WHILE- program on the left (variable numbers start at 0):
test read A {
while hd A {
B:= cons A nil ;
A:= tl A
} ]] } ,1] write B
Typical mistakes
[0,
[ [while,[hd,[var,0]],[
[:=,1,[cons,[var,0],[quote,nil]] ],
[:=,0,[tl,[var,0]]]
]
• Some students confused the answer with “self-referencing program”
• Some students wrote something about diagonalisation or decision procedures.
2. For each tree in D tick ‘yes’ if it represents a list of numbers and write the corre- sponding list – e.g. [1,2,3] – in the provided space, or tick ‘no’ otherwise.
⟨nil.nil⟩ ⟨⟨⟨nil.nil⟩.nil⟩.nil⟩ ⟨⟨nil.nil⟩.⟨nil.nil⟩⟩ ⟨nil.⟨⟨nil.nil⟩.nil⟩⟩
Typical mistakes
√yes [0] no
yes √yes √yes
√ no [1,0] no [0,1] no
• sometimes students have added an extra 0 to their lists, probably thinking the terminator (rightmost nil) is part of the list.
• The third case has sometimes been misidentified with [1,1] or wrongly consid- ered not to be a list of numbers.
3. Complete the sentence: “The WHILE language has just the right mix of
simplicity and expressive power (or expressivity) .” (Neil Jones)
Typical mistakes
• Most students got this right, some wrote “expressiveness” which was accepted.
• Some students wrote things like “self-expression” or “simplexity” and got marks for it but not full marks.
4. Complete: “To show that HALT is WHILE semi-decidable we programmed a self-interpreter in WHILE.”
Typical mistakes
• Some students confused the answer with “self-referencing program”
• Some students wrote something about diagonalisation or decision procedures.
5. Complete: “If problem B is known to be undecidable we can show also that problem A
is undecidable by showing that B ≤rec A (B is effectively reducible to A) .”
Typical mistakes
• Many students confused the direction and wrote A ≤rec B (they got 4 marks though!)
• Some students (cleverly) wrote “by showing that A is equivalent to B” which was not the intended answer but cannot be faulted so they got full marks too.
6. 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 ”.
Typical mistakes
none.
7. What specific feature must a language offer such that we can write interpreters, compilers and specialisers in it? programs-as-data
8. WhatisEconsXX{X:2}? ⟨nil.nil⟩ √⟨2.2⟩ ⊥ 4 4 Typical mistakes
• Many students got this right, but some ticked ⊥ or 4.
9. Complete the definition of the operational semantics of a specific RAM assignment:
p⊢(l,σ)→( l+1 ,σ[ i := σ(σ(j))) ifIl=Xi:=
• Some students wrote l instead of l + 1 and some wrote illegible stuff.
• For the store update, many students wrote Xi instead of σ(i) and so on. • Some forgot about the extra σ( ) of the indirect addressing.
10. Which of the problems below can be shown to be undecidable and why? Tick one box per question.
(a) A={d∈D|d=pandtimeWHILE(d)≤10×|d|3 }
√
p
decidable by giving decision procedure decidable by Rice’s Theorem undecidable by Rice’s theorem undecidable by other reason
(b) A={d∈D|d=pandpisadecisionprocedureforPRIMEnumbers}
decidable by giving decision procedure decidable by Rice’s Theorem √ undecidable by Rice’s theorem undecidable by other reason
Typical mistakes
• All kinds of wrong guesses.
• For (a) the answer “decidable by Rice’s Theorem” got only one mark deducted because decidable is correct. But note that Rice’s Theorem cannot be used to show that a problem about programs is decidable
• For (b) the answer “undecidable by other reason ” got only one mark deducted because undecidable is correct.
11. Complete the following judgements about WHILE expressions and statements (n is a natural number) making correct use of the already given arithmetic operations. Use (a) in (b) and (a),(b) in (c).
(a) T X = 1
(b) X:=tlX⊢time {X:n}⇒ 1 + 1 + (a) = 3
(c) whileX{X:=tlX}⊢time {X:7}⇒(7×(1+(a)+(b))+1+(a))= 37 Typical mistakes
• (a) was answered correctly by most. A few wrote weird things like n or time.
• (b) was answered correctly by many. However, n – and variations thereof –
popped up more times now.
• (c) was done perfectly by very few. Many could not even say how often the loop was executed. This was the first factor before the ×. Many did not think of the time it takes to evaluate the card (every time!) and then +1 for checking whether it is nil or not.
12. Assume we have a WHILE-program p such that timeWHILE(d) = 2|d|2 + 2|d| + 1. p
Tick all statements that are correct.
√ p ∈ WHILEtime(f ) where f (n) = n3 + 56 √ p has a time bound in O(n2)
f(n)=n9 +2isatimeboundforp
Typical mistakes
p ∈ WHILElintime
p has a time bound in O(nlogn)
p∈PWHILE
• The correct two answers were ticked by many students.
• Many students ticked also n9 + 2 as time bound which is not the case for small
input.
• Also, still many students ticked the PWHILE answer, despite the fact that we mentioned often in lectures and exercises that this is a problem class (and not a program class).
13. Define formally or informally (in any case precisely) the class PWHILE: This is the class of problems decidable by a WHILE-program in polynomial time .
Typical mistakes
• Quite a large number of students confused this with the class of programs that run in polynomial time (3 marks for this).
• Some even wrote about a polynomial or linear time bound for the WHILE- language, though it’s not clear what that means even.
• Quote a number of students also did not care to answer this or wrote some fantasy text.
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
TIMEWH1LE(a × n) .” Typical mistakes
• Anumberofstudentschosenottoanswerthisbutquiteanumbergotitperfectly right.
• Some students just wrote TIMEWH1LE and got something for it.
• Some students just wrote a × n and got something for it.
• Some students wrote A in TIMEWH1LE(b × n) and got something for it.
15. Complete Cook’s thesis: “All ‘reasonable’ sequential notions of computa- tion can simulate each other up to polynomial time difference .”
Typical mistakes
• Quite a number of students confused this with the Church-Turing Thesis.
• Many students got at least “polynomial time (difference)” right (for 3 marks). The “sequential” was correctly given by only a few. “Non-parallel ” was accepted too.
• Note that up to “Ptime” is only not a clear answer (1 mark).
• All kinds of strange answers were given, also linear time was mentioned occa-
sionally.
16. Are the following statements true, false or unknown? Tick one box per statement.
Parsing is in P PRAM = PTM
WHILE ≼lintime GOTO
Travelling Salesman Problem is in P Complement of HALT is in EXP
Typical mistakes
• All kinds of wrong answers were given here.
√ true false unknown √ true false unknown √ true false unknown true false √ unknown true √ false unknown
• Very often “TSP is in P” was (wrongly) declared “true” or “false”.
• Very often “Complement of HALT is in EXP” was (wrongly) declared “un- known”. Note that the Halting Problem (and complement thereof) are not even decidable!
17. “IfAisinPandBisinP,thenA∩B(theintersectionofAandB)isinP”.
This statement is √ true false unknown (Tick one box.)
Explain your answer: (1) A ∩ B is decidable follows from A decidable and B
decidable running their decision procedures sequentially (2) It runs in polynomial time since the addition of two polynomials is a polynomial.
Typical mistakes
• This was a slightly difficult question.
• Most students ticked correctly ‘yes’.
• But nobody really gave a fully acceptable reason.
• Many students just wrote that this “must obviously” be the case. But it is not. One has to prove this.
• Many students confused “AisinP” with A is an element of problem P. But obviously A and B must be problems, and thus sets (otherwise the union would not make sense).