University of Sussex 4 May 2018
Limits of Computation Test
→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 { [0,
while hd A {
B:= cons A nil ;
A:= tl A
} }
write B
]
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⟩⟩
yes yes yes yes
no no no no
3. Complete the sentence: “The WHILE language has just the right mix of
and .” (Neil Jones)
4. Complete: “To show that HALT is WHILE semi-decidable we programmed a
in WHILE.
5. Complete: “If problem B is known to be undecidable we can show also that problem A is undecidable by showing that .”
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 ”.
7. What specific feature must a language offer such that we can write interpreters, com- pilers and specialisers in it?
8. WhatisEconsXX{X:2}? ⟨nil.nil⟩ ⟨2.2⟩ ⊥ 4 4
9. Complete the definition of the operational semantics of a specific RAM assignment:
p⊢(l,σ)→( ,σ[ := ]) ifIl =Xi:=
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
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 =
(b) X:=tlX⊢time {X:n}⇒ + + =
(c) whileX{X:=tlX}⊢time {X:7}⇒( ×( + +
12. Assume we have a WHILE-program p such that timeWHILE(d) = 2|d|2 + 2|d| + 1.
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
p
p ∈ WHILElintime
p has a time bound in O(nlogn)
p∈PWHILE
13. Define formally or informally (in any case precisely) the class PWHILE:
)+ )=
. 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 .”
15. Complete Cook’s thesis: “All ‘reasonable’ notions of computation can simulate each other up to
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
true false unknown true false unknown true false unknown true false unknown true false unknown
17. “IfAisinPandBisinP,thenA∩B(theintersectionofAandB)isinP”. This statement is true false unknown (Tick one box.)
Explain your answer: