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:
[[var,0],
[ [:=,[var,1],
[cons,[var,0],[quote,nil]]],
[while,[var,1],[]]
], [var,1]]
prog read X {
} write Y
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 yes
no no no no
3. Complete the sentence: “WHILE programs are a good choice for effective procedures because WHILE has just the right mix of
and .” [Neil Jones]
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 thesis”.
5. Complete the definition of the operational semantics of the given RAM assignment:
p⊢(l,σ)→( ,σ[ ]) ifIl =
6. Complete the sentence: “The problem whether any given L-program p
is called the Halting Problem (for L). This problem is un .”
7. Complete: “To show that a problem A is undecidable it suffices to show that
is effectively reducible to .”
8. Which of the following problems are undecidable? Tick the ones that are.
Postman Parsing Tiling Halting Graph Colouring Primes
P.T.O
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}
p
decidable
undecidable by Rice’s theorem undecidable by other reason
(b) A={d∈D|d=pandpcompilesWHILEintoCM-programs} decidable
undecidable by Rice’s theorem undecidable by other reason
10. Complete the sentence: “ If E is a WHILE-expression, T E denotes
; for instance, T cons hd X nil evaluates to
11. Complete the definition:
C;S⊢time σ⇒t+t′ if C⊢time σ⇒t, C⊢ and S ⊢time
12. Define formally or informally (in any case precisely) the class LINL:
.”
.
.
13. True, false or unknown? Tick the boxes accordingly. The Postman problem is feasible
PGOTO = PTM
WHILE ≼lintime GOTO
true false true false true false true false
unknown unknown unknown unknown
There is an A ∈ EXP such that A ∈/ P
14. Fill in the gaps in the Linear Hierarchy Theorem: “There is a constant b such that
for a ≥ 1 there is a problem A in TIMEWH1LE(a×b×n)
that is not in .” 15. Assume we have a WHILE-program p such that timeWHILE(d) = 12|d|3 + 3|d| + 4.
Tick only the statements that are correct.
p∈TIMEWHILE(f)wheref(n)=n3+10n+10
p∈TIMEWHILE(O(n3 +n+6))
p∈TIMEWHILE(f)wheref(n)=9n2+512
p∈LINWHILE p∈PWHILE
p∈TIMEWHILE(O(n3))
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
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:
p
.