THE UNIVERSITY OF SUSSEX
BSc FINAL YEAR and MComp THIRD YEAR EXAMINATION 2020
JUNE 2020 (A2)
Limits of Computation
Date: Wednesday, 3 June 2020
24 Hour Window starts at: 14.00
Exam Duration: 3 hours (including time for scanning and uploading)
Candidates should answer TWO questions out of THREE. If all three questions are attempted only the first two answers will be marked.
Each question is worth 50 marks.
Write your answers on A4 paper, scan and save as a single PDF file and upload to Canvas
PDF file name: candidate number module
Please make sure that your submission includes the following:
Your candidate number (Do not put your name on your paper) The title of the module and the module code
Academic Integrity Statement
You are reminded that you should not access online materials, notes etc. during this examination or discuss this assessment with others before the end of its 24 hour window.
By submitting this assessment you confirm that you have read the above Statement and are responsible for understanding and complying with Academic Misconduct regulations as they relate to this assessment.
1. This (a)
Limits of Computation
question is about WHILE and other notions of effective computability.
The WHILE-language has one built-in data type, the type of binary trees where leaves contain always atom nil (for pure WHILE). Explain briefly
Whyisitimportanttohaveacomputationmodelthatsupportsprograms- as-data? [6 marks]
Consider now computability of functions on natural numbers, i.e. functions of type N → N⊥.
why this is sufficient to define the notion of computability. Let foo be the following pure WHILE-program:
foo read L {
out := cons nil nil;
X := hd L; if X
{ L:= tl L
out := nil;
i. What is foo
Explain the semantical difference between a WHILE-expression and a WHILE-command. [4 marks]
Write a WHILE-program that has the following data representation:
[while,[var,0],[ [:=,1,[cons,[hd,[var,0]],[quote,nil]] ],
[:=,0,[tl,[var,0]] ]
([1]), respectively? No [2 marks]
(1) and foo explanation required.
ii. Give the semantics of the program foo, in other words give a precise WHILE
definition of the partial function foo : D → D⊥. Do not re- explain or narrate the program. [6 marks]
[10 marks]
Limits of Computation G5029
i. For each of the following functions f on natural numbers state whether they are WHILE-computable or not. Briefly explain your answer in a sentence.
A. f(n) = nn···n
B. f(n)=maxKn where
Kn = {k∈N | p (nil)=k for program p s.t. |p| ≤ n}
1 iff p (p) ̸= ⊥ where p is the n-th WHILE-program 0 otherwise
D. f(n)=⊥foralln∈N
E. f(n)=minKn where
(nil)=k for program p s.t. |p| ≤ n}
[10 marks]
Kn = {k∈N | p
ii. Does computability of such functions depend on whether they are
implementedinWHILEorRAM?Brieflyexplainyouranswer. [3marks]
iii. If we removed the conditional statement (if then else) from the pure WHILE-language, could we still compute the same functions of type N → N⊥ that we did with the conditional? Explain your answer briefly. [5 marks]
3 Turn over/
G5029 Limits of Computation
2. This question is about semi-decidability, decidability, and various forms of reduction.
(a) For each of the following problems state whether it is WHILE-semi- decidable or not. Explain your answer in one sentence.
i. NAT: Given an element of D, does it encode a natural number? ii. HALT (the halting problem for WHILE);
iii. The complement of HALT;
iv. The complement of the Traveling Salesman Problem.
(b) For the following sets A ⊆ WHILE-data state whether they are WHILE- decidable or undecidable 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 }
ii. A = {p | p = read X {while true {}} write X} . [4 marks] iii. A = {[p,k] | p ∈ O(nk)} [4 marks]
(c) This question addresses the importance of effective problem reduction in computability theory.
i. For each of the following statements say whether the given effective reductionsfromA⊆DtoB⊆D,A≤rec B,aretrueorfalse. Explain each answer briefly. In case where the answer is true this explanation should be a description of the reduction function.
A. {1,2,4}≤rec HALT
B. {n|n∈N∧nisodd}≤rec {n|n∈N∧niseven} C. {nil} ≤rec HALT
D. HALT ≤rec {nil}
E. D\ HALT ≤rec {nil}
[10 marks]
ii. Explain in one or two sentences only the difference between effectiveproblemreductionandpolynomialtimereduction. [5marks]
(d) For each of the following statements about the recursion theorem say whether it is true or false. Explain your answer in one sentence.
i. The recursion theorem implies that there exists a WHILE program that returns its own description as data whatever the input.
ii. The recursion theorem does not apply to Java.
iii. The recursion theorem implies that any programming language meeting the theorem’s assumptions allows indirectly for recursive program definitions.
Programming Help
Limits of Computation G5029
(e) For each of the following problems state whether they are closed under the given operation. Explain your answer briefly.
i. If A and B are semi-decidable, is the set C = A∩B, i.e. the intersection of A and B, semi-decidable? [3 marks]
ii. if A ⊆ N is decidable, is the set of all identical pairs of numbers, i.e. { (a, a) | a ∈ A} decidable? [3 marks]
iii. if A ⊆ N is decidable, is the set of all numbers for which the busy-beaver function returns a number in A that is smaller than 500 decidable, i.e. { a | a ∈ A ∧ BB (a) < 500 } decidable? [3 marks]
5 Turn over/
G5029 Limits of Computation
3. This question is about complexity.
(a) Afunctionf :N→Nisatimebound foranL-programpif,andonlyif, for all input d ∈ L−data it holds that timeLp(d) ≤ f(|d|) where |d| is the size of d.
i. How does one measure the size of d, |d|, for d ∈ WHILE−data? [2 marks]
ii. In which situation do we have timeLp(d) = ⊥? [2 marks]
iii. Explain why it makes a difference for the time bound of a WHILE- program p on natural numbers whether p uses natural numbers in unary or decimal representation, i.e. whether it encodes a number like 12 as 12 or as a list [1, 2] where denotes the standard encoding of data as presented in lectures. [6 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. Give a short reason for each answer (one sentence suffices).
i. The Halting Problem is in P.
ii. NP ⊆ EXP
iii. P ⊆ NP
iv. WHILE≼lintime TM
v. The Satisfiability Problem (SAT) is in P.
vi. Max-Cut ≤P Integer Programming.
vii. The 0-1 Knapsack Problem is in P if one represents integers as unary numbers.
viii. NPSRAM ̸= NPWHILE
ix. WHILE ≼lintime WH1LE.
x. (The optimisation problem version of) TSP is not in APX.
[20 marks]
(c) A sequence s is a subsequence of a sequence t if s can be obtained from t by deleting some (maybe none) elements in t. For instance, the sequence 1,4,7, the sequence 2,3,4,6 and sequence 4,7 are all subsequences of 1, 2, 3, 4, 5, 6, 7, respectively. Subsequence 1, 4, 7 is obtained by deleting 2, 3, 5 and 6; subsequence 2, 3, 4, 6 is obtained by deleting 1, 4, 5 and 7; subsequence 4, 7 is obtained by deleting 1, 2, 3, 5 and 6.
The common subsequence problem (CSP) is the following decision problem: given a set of finite sequences s1, . . . , sn (over a given finite alphabet), is there a sequence s of length at least K such that s is a subsequence of each sequence s1,. . . , sn?
Show that CSP is in NP.
Github
Limits of Computation G5029
(d) Argue that PWHILE is closed under complement, i.e. argue that the following holds:
IfAisinPWHILE,thenA’scomplement,D\A,isalsoinPWHILE. [6marks]
(e) A sequence s is a subsequence of a sequence t if s can be obtained from t by deleting some (maybe none) elements in t as set out in Question 3(c).
The increasing subsequence problem (ISP) is the following decision problem: given a sequence of integer numbers s and a number K, is there a sorted subsequence of s that has at least K elements? By sorted we mean that the integers in the sequence appear in ascending order. For instance, for s = 4,1,8,2,1,1,5 and K = 3, the answer is YES as 1, 2, 5 is an increasing subsequence of s; for K = 4 the answer is YES, as 1, 1, 1, 5 is an increasing subsequence of s. For any K ≥ 5 the answer would be NO.
Show that ISP ≤P CSP, i.e. that ISP is polynomially reducible to CSP – where CSP was explained in Question 3c) – by answering the following questions:
i. Describe the required reduction function f. [4 marks]
ii. Argue that the function f you defined satisfies the condition of a reduction function, i.e. x ∈ ISP iff f(x) ∈ CSP (you will need to explain what x is). [2 marks]
You don’t have to show that the function is computable in polynomial time or total.
7 End of Paper
Code Help