Define precisely what we mean when we write L1 P L2. [4 marks] (b) What is the

No answer yet for this question. Ask a Tutor

Question:

Define precisely what we mean when we write L1 ≤P L2. [4 marks]
(b) What is the difference between NP-completeness and NP-hardness? [2 marks]
(c) Let 3COL denote the following decision problem.
Given a graph G = (V, E), is it 3-colourable?
(i) Is 3COL in NP? Why? [2 marks]
(ii) Show that 3SAT ≤P 3COL. [10 marks]
(iii) Argue that 3COL is NP-complete. [2 marks]
2
CST.2009.6.3
3 Computation Theory
(a) What is meant by a state (or configuration) of a register machine? [2 marks]
(b) A register machine program Prog is said to loop at x ∈ N if, when started
with register R1 containing x and all other registers set to zero, the sequence
of states Prog computes contains the same non-halted state at two different
times.
(i) At which x does the following program loop?
R HALT _
0
[2 marks]
(ii) Show that if Prog loops at x, then the computation of Prog does not halt
when started with register R1 containing x and all other registers set to
zero. Is the converse true? [4 marks]
(iii) Consider the set S = {he, xi | Proge
loops at x} of codes of pairs of
numbers (e, x) such that the register machine program Proge with index
e loops at x. By adapting the usual proof of undecidability of the halting
problem, or otherwise, show that S is an undecidable set of numbers.
[Hint: if M were a register machine that decided membership of S, first
consider replacing each HALT instruction (and each jump to a label with
no instruction) with the program in part (i).] [12 marks]
3 (TURN OVER)
CST.2009.6.4
4 Computation Theory
(a) Define what it means for a subset S ⊆ N to be a recursively enumerable set of
numbers. [2 marks]
(b) Show that if S and S
0
are recursively enumerable sets of numbers, then so are
the following sets (where hx, yi = 2x
(2y + 1) − 1).
(i) S1 = {x | x ∈ S or x ∈ S
0
}
(ii) S2 = {hx, x0
i | x ∈ S and x
0 ∈ S
0
}
(iii) S3 = {x | hx, x0
i ∈ S for some x
0 ∈ N}
(iv) S4 = {x | x ∈ S and x ∈ S
0
}
Any standard results about partial recursive functions you use should be clearly
stated, but need not be proved. [16 marks]
(c) Give an example of a subset S ⊆ N that is not recursively enumerable.
[2 marks]
4
CST.2009.6.5
5 Foundations of Functional Programming
(a) Define the Church numerals giving the encodings of zero 0, one 1 and an
arbitrary number n. [3 marks]
(b) Define λ-terms to perform the following operations on Church numerals. You
may assume standard definitions for Booleans (true, false, if, and, and or) and
pairs (pair, fst, and snd). For each part, you may assume solutions to the
previous parts of the question. You may not use a fixed-point combinator.
(i) Test for zero. [2 marks]
(ii) Successor. [2 marks]
(iii) Predecessor (where predecessor of zero is zero). [4 marks]
(iv) Less than or equal. [3 marks]
(v) Equality. [2 marks]
(vi) Successor modulus n (where succn n m = 0 if n = m + 1, and
succn n m = m + 1 otherwise). [2 marks]
(vii)Modulus (e.g mod n m = m mod n). [2 marks]
5 (TURN OVER)
CST.2009.6.6
6 Foundations of Functional Programming
(a) Define what it means for a λ-calculus term to be in normal form. Is it possible
for a λ-term to have two normal forms that are not α-equivalent? Provide
justification for your answer. [3 marks]
(b) For each of the following, give an example of a λ-term that
(i) is in normal form;
(ii) is not in normal form but has a normal form; and
(iii) does not have a normal form.
For (ii), you should also present the term's normal form, and for (iii) you
should show that the term does not have a normal form