Candidate Number
THE UNIVERSITY OF SUSSEX
BSc FINAL YEAR EXAMINATION MComp THIRD YEAR EXAMINATION May/June 2017 (A2)
LIMITS OF COMPUTATION
Assessment Period: May/June 2017 (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
1. This (a)
(b) (c)
LIMITS OF COMPUTATION
question is about various notions of effective computability.
We used the WHILE-language to describe effective computability. What kind of commands (statements) does this language provide in its pure form without extensions? [3 marks]
Explain the concept of indirect addressing used by the RAM computation
(d)
(e)
(f)
(g)
Assume c1 is a compiler from S to T written in L . Assume further c2 is a compiler from L to M written in C. What do we get if we compile c1 using c2? Be as precise as possible. [4 marks]
Assume that languages S and T have the same datatype. What is the correctness condition for a compiling function (i.e. the semantics of a compiler) c from language S to T? Provide either the formal definition or an equivalently precise explanation. [6 marks]
Can we add a new instruction to the instruction set of a standard Turing Machine, such that the resulting new Turing Machines, let’s call them Turing Machines Plus, can decide more problems than the standard type of Turing Machines? Explain your answer. [5 marks]
Can we remove an instruction from the definition of standard Turing Machines, such that the resulting new Turing Machines, let’s call them Turing Machines Minus, can decide fewer problems than the standard type of Turing Machines? Explain your answer. [5 marks]
model. Why is this needed at all?
Let the following WHILE-program myprog be as follows:
myprog read X {
while X {
Z := cons nil Z;
X := tl X
};
[6 marks]
Z := tl Z
write Z
}
i. Assuming that we start counting variables from 0, give the program- as-data representation of myprog. [13 marks]
ii. What is E tl X {X : 4,Y : 0}? [3 marks] WHILE
iii. What is myprog (n) for any n ∈ N? Explain your result briefly, but you do not need to give a formal derivation. [5 marks]
2
2. This (a)
(b)
LIMITS OF COMPUTATION G5029
question is about decidability and semi-decidability.
Define precisely what it means for a set A ⊆ WHILE-data to be WHILE- semi-decidable. [7 marks]
Which of the following problems are WHILE-decidable? (No explanation needed.)
i. Halting problem
ii. Complement of the Halting problem
iii. Travelling Salesman problem iv. Postman problem
v. Tiling problem
vi. The problem whether a natural number is a prime number
[6 marks]
Give a problem (set) that is semi-decidable but not decidable. [3 marks]
What proof technique (besides proof-by-contradiction) is used in the proof that the Halting Problem is undecidable? No explanation is required. [2 marks]
What proof technique (besides proof-by-contradiction) is used in the proof of Rice’s Theorem? Explain what this technique is applied to. You don’t have to explain the technique itself. [4 marks]
Explain 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. Here p denotes the encoding of a WHILE-program as WHILE-data.
i. A = {p | WHILE-program p returns nil if its input encodes a WHILE-program that contains one or more while loops } [6 marks]
ii. A = {p | WHILE-program p contains no while loops } [6 marks] iii. A = {p | WHILE-program p returns nil for finitely many inputs }
[6 marks] Explain why an arbitrarily large and complicated but finite set A ⊆ WHILE-
data is always WHILE-decidable. [4 marks]
Recall that the set A ∪ B contains the elements of A as well as the elements of B and nothing else. Let A ⊆ WHILE-data and B ⊆ WHILE- data. If A and B are both semi-decidable, is their union, A ∪ B, also semi-decidable? Give a reasonable argument (no full proof required) for your answer. [6 marks]
(c) (d)
(e)
(f)
(g) (h)
3 Turn over/
G5029
3. This (a)
(b) (c)
(d)
(e)
LIMITS OF COMPUTATION
question is about complexity. Consider WHILEtime(f).
i. Give a (precise) definition of the class WHILEtime(f). [5 marks]
ii. Assume you have two WHILE-programs p ∈ WHILEtime(n2+13) and q ∈ WHILEtime(34n+12) that have the same semantics. Which one would you use and why? [6 marks]
What does the N in NP stand for? What does the P stand for? [4 marks] The Travelling Salesman problem (TSP) is NP-complete.
i. What does the statement above mean exactly? [5 marks]
ii. Referring to TSP as example, explain to what extent approximation algorithms are a useful means to solve NP-complete problems
(viewed as optimisation problems). [8 marks]
Which of the following problems are known to be NP-complete?
i. 0-1 Knapsack problem
ii. Complement of the Halting problem
iii. Graph Colouring problem iv. Tiling problem
v. Postman problem
vi. Factorisation Problem
[6 marks]
In the following give a rough description of how you would prove the statement in question. You do not have to give a proof, but you are supposed to sketch the required plan, i.e. which activity you would need to carry out and/or which theorems you would use in which way. Be as precise as possible.
i. There exists a problem that can be decided by a WHILE-program in exponential time but not in polynomial time. [5 marks]
ii. A certain (fixed) problem A, the details shall not be important, is in LINWHILE. [5 marks]
iii. A certain (fixed) problem A, the details shall not be important, can’t possibly be in PWHILE unless P = NP. [6 marks]
4 End of Paper