Home Page > > Details

Ghostwriter G5029 Limits of Computation BSc FINAL YEAR EXAMINATION May/June 2019 (A2)Help With



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 Satisability Problem (SAT) is in P.

iv. The Satisability 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]

Contact Us - Email:99515681@qq.com    WeChat:codinghelp
Programming Assignment Help!