Candidate Number
THE UNIVERSITY OF SUSSEX
BSc and MComp FINAL YEAR EXAMINATION May/June 2018 (A2)
Limits of Computation
Assessment Period: May/June 2018 (A2)
DO NOT TURN OVER UNTIL INSTRUCTED TO BY THE LEAD INVIGILATOR
Candidates should answer TWO questions out of THREE. If all three questions are attempted only the first two answers will be marked.
The time allowed is TWO hours.
Each question is worth 50 marks.
At the end of the examination the question paper and any answer books/answer sheets, used or unused, will be collected from you before you leave the examination room.
G5029
G5029 Limits of Computation
1. This question is about SRAM, WHILE and other notions of effective computability.
(a) Describe precisely what the judgment
p ⊢ (l,σ) → (l′,σ′)
means for an SRAM program p. Recall that l and l′ are program labels and that σ and σ′ are stores that map natural numbers to natural numbers. [5 marks]
(b) Let a specific SRAM program p and a label l be given such that p(l) = Xi:=
p ⊢ (l,σ) → (l′,σ′)
holds for p, l and σ as described above. [5 marks]
(c) Do the computability results we proved for the WHILE-language also hold for SRAM? Explain your answer in one sentence. [4 marks]
(d) The semantics of a WHILE command C is expressed by the judgement C ⊢ σ → σ′
where σ and σ′ are stores for WHILE. For instance, [X → 2, Y → nil] describes a store that maps program variable X to value 2 and variable Y to value nil. Recall that n is the encoding of number n as WHILE-data.
i. Give an example of a single WHILE statement C such that C ⊢[X →nil]→[X →2]
[4 marks]
ii. Give an example of a single WHILE statement C such that there is
no store σ with C ⊢ [X → nil] → σ [4 marks]
iii. Compute the value of E cons tl X nil [X → 3]. Present the final result as a list that contains only natural numbers. Show your working. [6 marks]
(e) Assuming that we start counting variables from 0, give the program-as- data representation of the following WHILE program:
prog read X {
X:= tl X;
if Y { Y:= cons X Y }
else { X:= tl X ; Y:= nil }
}
write Y
2
[10 marks]
Limits of Computation G5029
(f) Consider the language REPEAT which has the same program structure and expressions E as the WHILE-language but whose commands do not contain a while statement but instead a statement of the form:
repeat E times B
where, as usual, E represents expressions and B is a block of the form {C1; . . . ;Cn}. Variables and expressions in REPEAT are exactly as in WHILE, and therefore the stores used in the semantics of REPEAT are like the ones used in WHILE. Also the semantics of assignment and sequential composition in REPEAT are exactly as they are in WHILE.
Assuming that E evaluates to n, executing repeat E times B means executing its body B exactly n times (if n = 0, B is not executed at all). If, however, E does not evaluate to a natural number, the repeat statement terminates immediately.
Consider the REPEAT program test:
test read X {
Y := nil;
repeat X times { Y:= cons nil Y }
}
write Y
For input 0 the program test returns 0, for input 1 it returns 1,
for input 2 it returns 2, and so on.
Here is the formal semantics of the repeat statement for the case that
the expression argument does not evaluate to a natural number:
repeat E times C⊢σ→σifthereisnok∈NsuchthatEEσ=k Complete the formal semantics of the repeat statement by giving the
missing clause(s). [8 marks]
(g) Can we program a self-interpreter for language REPEAT like we have
done for WHILE? Explain your answer briefly. [4 marks]
3 Turn over/
G5029 Limits of Computation
2. This question is about semidecidability and decidability.
In this question we refer to a programming language L. For any L-program p, the semantics of p is given by the semantic function for L:
L
A ⊆ L-data to be “L-semidecidable”. [6 marks]
(b) Give an example (without explanation) of a problem that is semi-
decidable but not decidable. [2 marks]
(c) Without having to know what L is exactly (we assume only it is not trivial), we can always give TWO examples of L-decidable problems. Which are they? (No explanation required) [4 marks]
(d) Assume f is a function of type L-data → L-data⊥. Which minimal assumptions about f do we have to make to ensure that the following statement is correct:
“{x ∈ L-data | f(x) = x} is L-decidable.”
With your chosen assumptions, argue briefly why the statement holds. [7 marks]
(e) Assume now L is WHILE. Which of the following problems are WHILE- undecidable? (No explanation needed.)
i. Halting problem for WHILE-programs
ii. Complement of the Travelling Salesman problem
iii. The problem whether two given WHILE program have the same semantics
p :L−data→L−data⊥
(a) Referring to the semantic function for L, explain what it means for a set
iv. Shortest Path problem
v. Tiling problem
vi. Matching Problem
[6 marks]
(f) Decide for the following sets A ⊆ WHILE-data whether they are WHILE- decidable. For each case, explain your answer. In cases where A is decidable, this explanation should consist of a description of the decision procedure. Recall that n is the encoding of number n as WHILE-data and p the encoding of a WHILE-program as WHILE-data.
i. A = {p | p is a WHILE-program and p is a list of length 13 } [6 marks]
ii. A = {d | WHILE-program Prog halts when run on input d} where Prog is a WHILE-program with semantics
Prog
WHILE
(d) =
m−n ifd=(m.n)andm≥n, 0 if d = (m.n) and m < n,
undefined otherwise
4
[6 marks]
Limits of Computation G5029
iii. A = {p | WHILE-program p returns p for any input } [6 marks]
(g) Briefly explain the impact Rice’s Theorem has on programming languages and their development environments (tools) for programmers. [7 marks]
5 Turn over/
G5029
3. This
(a) (b)
Limits of Computation
question is about complexity.
Define the complexity class PWHILE. [4 marks]
For each of the statements below state whether it is known to be true, known to be false, or whether it is unknown whether it is true or false. You do not have to give reasons for your answer.
1 The Tiling problem is NP-complete.
2 SAT (Cook’s Satisfiability Problem) can be reduced to TSP (the Traveling Salesman Problem) in polynomial time.
3 PTM = PRAM
4 TSP (the Traveling Salesman Problem) can be reduced to SAT
(Cook’s Satisfiability Problem) in polynomial time.
5 TSP (the Traveling Salesman Problem) can be reduced to the Postman problem in polynomial time.
6 P ⊆ NP.
7 The Postman problem is in P.
8 TSP (the Traveling Salesman Problem) is in P.
9 Quantum Computers can solve NP-complete problems in polynomial
(c) (d)
Explain what the Cook-Karp (also known as Cobham-Edmonds) thesis says. What are the arguments for and against this thesis? [8 marks]
Consider the following optimisation problem which is a minimisation problem:
Bin Packing Opt: Assume we have n items, called 1,...,n, each of which has a nonnegative integer size, called ai. Assume further we have an arbitrary number of ‘bins’ of capacity k, which means that each bin can hold items only if the sum of the size of those items is less or equal k. Minimise the number of bins that can hold all items 1, . . . , n.
Forinstance,ifn=3witha1 =4,a2 =3anda3 =9andk=10thenthe minimal number of bins is 2. The first bin, for example, can hold item 3 but nothing else as a3 = 9 ≤ 10, and the second bin can hold items 1 and2,asa1 +a2 =7≤10.
All numbers ai and k are represented in binary format.
i. In general, what condition must an algorithm for a minimisation problem satisfy to be called an α-approximation algorithm ? Your explanation should include a definition of the approximation factor of such an algorithm. [4 marks]
ii. Sketch a simple polynomial approximation algorithm for the optimisation problem Bin Packing Opt above with an approximation factor of 2. Hint: it’s not difficult to get this factor (it’s almost automatic) and you don’t have to prove it. To make sure your
time.
[9 marks]
6
Limits of Computation G5029
algorithm achieves this factor just ensure that it is never the case that two bins exist that are less than half full. [6 marks]
iii. In which optimisation problem class must Bin Packing Opt be according to the above? Briefly explain why. [4 marks]
(e) Consider now the decision problem version of Bin Packing:
Bin Packing: Assume we have n items, called 1, . . . , n, each of which has a nonnegative integer size, called ai. Is it possible to place all items 1,...,n in M bins that all have the same capacity k, i.e. each bin can only hold items the sum of their size is less or equal k? We can assume here that M < n otherwise the problem is trivial.
All numbers ai, M and k are represented in binary format.
Explain why Bin Packing (the decision problem!) is in NP. Any algorithm to show this can be sketched, but any runtime information must be discussed thoroughly. [9 marks]
(f) What important result would follow if we could prove that NPWHILE was not closed under complement? Explain your answer briefly. [6 marks]
7 End of Paper