Candidate Number
THE UNIVERSITY OF SUSSEX
BSc FINAL YEAR EXAMINATION MComp THIRD YEAR EXAMINATION May/June 2019 (A2)
Limits of Computation
Assessment Period: May/June 2019 (A2)
G5029
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 Limits of Computation
1. This question is about WHILE, its semantics, and other notions of effective computability.
(a) What does the judgment S ⊢ σ1 → σ2 mean for a list of WHILE-statements S and stores σ1 and σ2? [4 marks]
(b) Give the rule that defines the operational semantics of WHILE- assignments, i.e. for the judgement X := E ⊢ σ1 → σ2 define precisely what σ2 must be in terms of σ1. [4 marks]
(c) Regarding the semantics of WHILE, what does E E σ denote exactly? [3 marks]
(d) Give the semantic equation for E X σ where X is a variable. [3 marks]
(e) What is E cons X nil {X : 3}? As usual, n ∈ D denotes the encoding of natural number n. You do not have to show intermediate results. [2 marks]
(f) Give an example of a single WHILE-command C such that
C ⊢{X:n, Y:0}→{X:0, Y:ndiv2}
where n ∈ D denotes the encoding of natural number n and div denotes integer division without remainder. [7 marks]
(g) Assuming that we start counting variables from 0, give the program-as- data representation of the following WHILE-program:
prog read X {
Z:= nil;
X:= cons Z X;
if X { Y:= cons Y X }
}
write Y
(h) Whyisitimportanttohaveacomputationmodelthatsupportsprograms- as-data? [6 marks]
(i) List FOUR (different) notions of computation other than WHILE with which one can compute the same functions on natural numbers as one can with WHILE. [4 marks]
(j) Assume L-data = S-data and an L-program p which has the following property:
LS
p (d1,d2)=d1 (d2)
where (d1, d2) denotes pairing in L.
i. Describe informally what program p does (without restating the
equation above in words). [4 marks] ii. Besides L-data = S-data, what other implicit assumption(s) are
necessary for p to be well defined by the above? [2 marks]
[11 marks]
2
Limits of Computation G5029
2. This question is about semi-decidability, decidability, the recursion theorem, and reduction.
(a) Let A ⊆ D. Assume there exists a WHILE-program p such that the following holds:
WHILE
(d) = true if, and only if, d ∈ A.
(b) Give an example of a set A that has the property of Question 2(a).
p
What property does A have according to the above? [3 marks].
[2 marks]
(c) Answer each question below with ’YES’ or ’NO’. If your answer is ’YES’ provide ONE example of a problem (i.e. set) that has the given property combination.
i. Is there a set that is finite and decidable?
ii. Is there a set that is finite and undecidable?
iii. Is there a set that is infinite and decidable?
iv. Is there a set that is infinite and undecidable?
[2 marks] [2 marks] [2 marks] [2 marks]
(d) For the following sets A ⊆ WHILE-data state whether they are WHILE- decidable and explain your answer. In cases where A is decidable this explanation should consist of a description of the decision procedure. Recall that p denotes the encoding of WHILE-program p in D.
i. A = { p | p returns nil if its input encodes a natural number }
[5 marks]
ii. A={p|p=c}wherec∈Disfixed. [5marks]
(e) This question addresses the importance of effective problem reduction
in computability theory.
i. What is the definition of an effective problem reduction A ≤rec B
between two problems A ⊆ X and B ⊆ Y ? [6 marks]
ii. Consider the following problems: HALT (as given in lectures),
WHILE
A. ODD ≤rec EVEN B. EVEN ≤rec ODD C. EVEN ≤rec HALT D. HALT ≤rec EVEN E. HALT ≤rec HALT2
F. HALT2 ≤rec HALT
HALT2 = {p | p (p) ↓}, ODD = {n | n ∈ N is odd }, EVEN = {n | n ∈ N is even }.
Which of the following statements are correct? No explanation is required.
3
Turn over/
[6 marks]
/Question continued over
G5029
Limits of Computation
iii. Explain how the concept of reducibility is employed in computability and complexity theory. Hint: what kind of results can one prove with the help of (various forms of) reduction? [7 marks]
(f) Explain what Kleene’s Recursion Theorem tells us about the semantics
of programming languages.
[8 marks]
4
3. This question is about complexity.
i. Define P.
ii. Explain why the statement does not (need to) refer to a
class PL .
iii. Give an example of a problem in P.
iv. By what name is this statement known?
v. Give ONE argument in favour of this statement. vi. Give ONE argument against this statement.
[3 marks]
particular [6 marks]
[2 marks] [2 marks] [3 marks] [3 marks]
Limits of Computation G5029
(a) Consider the statement:
“P is the class of feasible problems.”
where the term “feasible problems” informally refers to problems that can be decided in an acceptable amount of time.
Answer the following questions in relation to this statement:
(b) For each of the following statements, state whether they are (known to be) true, (known to be) false, or whether the answer is currently still unknown. Accordingly, write as answer either true, false, or unknown, respectively.
For the true statements, and only for those, explain in one sentence why they are true (sometimes it may be best to cite a theorem or a result shown in the lectures).
i. Thereisabsuchforalla≥1itholdsthat: TIMEWH1LE(a × n) TIMEWH1LE(a × b × n)
ii. NP is closed under complement
iii. The Satisfiability Problem (SAT) is in P.
iv. The Satisfiability Problem (SAT) is NP-complete.
v. The Halting Problem is in NP.
vi. The complexity class P is robust regarding changes of the
underlying computational model.
vii. The Prime Factorisation Problem is in P.
viii. Quantum computers can solve NP-complete problems in polynomial
time. [16 marks]
(c) Discuss the approximability (in polynomial time) of the Travelling Salesman Problem (TSP). Here TSP is considered in the optimisation problem version rather than as decision problem. Address the general issue of approximability, and how TSP is special in that respect. Consider the situation for specific versions of TSP as well. Define any complexity classes you introduce in your answer. Marks will be assigned based on the correctness of your answer and the coverage of the various aspects. [15 marks]
5 End of Paper