G5029
BSc FINAL YEAR EXAMINATION
May/June 2019 (A2)
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 ‘EI σ denote exactly? [3 marks]
(d) Give the semantic equation for E ‘XI σ where X is a variable. [3 marks]
(e) What is E ‘cons X nilI {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 :「n div 2」}
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
[11 marks]
(h) Why is it important to have a computation model that supports programs- 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:
‘pIL (d1 ; d2 ) = ‘d1IS (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]
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:
‘pIWHILE (d) = true if, and only if, d ∈ A.
What property does A have according to the above? [3 marks].
(b) Give an example of a set A that has the property of Question 2(a). [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? [2 marks]
ii. Is there a set that is finite and undecidable? [2 marks]
iii. Is there a set that is infinite and decidable? [2 marks]
iv. Is there a set that is infinite and undecidable? [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 pin D.
i. A = {「p」| p returns nil ifits input encodes a natural number } [5 marks]
ii. A = {「p」|「p」= c} where c ∈ D is fixed. [5 marks]
(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), HALT2 = {「p」 | ‘pIWHILE (「p」) ↓}, ODD = {「n」 | n ∈ N is odd }, EVEN = {「n」| n ∈ N is even }.
Which of the following statements are correct? No explanation is required.
A. ODD rec EVEN
B. EVEN rec ODD
C. EVEN rec HALT
D. HALT rec EVEN
E. HALT rec HALT2
F. HALT2 rec HALT [6 marks]
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 the Kleene’s Recursion Theorem tells us about the semantics of programming languages. [8 marks]
3. This question is about complexity.
(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:
i. Define P. [3 marks]
ii. Explain why the statement does not (need to) refer to a particular class PL . [6 marks]
iii. Give an example of a problem in P. [2 marks]
iv. By what name is this statement known? [2 marks]
v. Give ONE argument in favour of this statement. [3 marks]
vi. Give ONE argument against this statement. [3 marks]
(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. There is a b such for all a ≥ 1 it holds that:
TIMEWH1 LE(a n) = TIMEWH1 LE(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]