University of Sussex 28 April 2017
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, 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 {
X:= tl X } }
write Y
]
2. Write the list below as element in D using only nils and ⟨ . ⟩-operations (linearly) [[0],[1]]
3. Complete: E cons E Fσ = .
4. Complete our definition of the Halting Problem below:
HALT = { [ p, d ] ∈ D | }
5. Complete the sentence: “For an L-program p, the term [p]L denotes the
of p which is a
function of type → .”
6. Every acceptable (i.e. reasonably expressive in a certain sense) programming language
automatically admits reflective programming. This is a consequence of
7. Complete the sentence: “ ‘Game of Life’ is a 2-dimensional automaton with four rules for: underpopulation, overcrowding, and .”
8. Complete: “To show that a problem A is decidable it suffices to show that is effectively reducible to
9. Which of the following problems are decidable? Tick the ones that are. TSP HALT Complement of HALT Matching Tiling
.
,
Primes P.T.O
.”
10. Which of the problems below can be shown to be undecidable (by Rice’s Theorem)? (a) A={d∈D|d=pandtimeWHILE(d)>|d| }
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
11. Complete the following judgements about WHILE expressions and statements (n is a
natural number). No need to show your working unless outlined:
T tl X =
X := tl X ⊢time {X:n} ⇒ whileX{X:=tlX}⊢time {X:4}⇒
Tick only the statements that are correct. p ∈ WHILEtime(f ) where f (n) = n3 + 456
phasatimeboundinO(n3) p∈PWHILE
13. Complete: L1 ≼linear−pg−ind L2 means that
14. Complete Cook’s thesis: “Computability
is equivalent for all (reasonable)
of computation.”
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 ThereisanA∈EXPsuchthatA∈/P
true false unknown true false unknown true false unknown true false unknown true false unknown
p
× +
12. Assume we have a WHILE-program p such that timeWHILE(d) = |d|3 + 5|d|2 + 2|d| + 8.
times loop body is executed
p
p ∈ WHILElintime
phasatimeboundinO(n5)
f(n)=n3 +16n2 isatimeboundforp
.
16. Complete: “Robustness” of P refers to the fact that decidability of problems in is independent of
.
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
” under the assumption P NP.