# CS代考计算机代写 University of Sussex 25 April 2016

University of Sussex 25 April 2016

Limits of Computation Test

→→→→→→→→→→→ → → CandidateNo.

• Please answer ALL questions by writing on THIS SHEET. You are not

allowed to use any other documents or devices.

• Please write your candidate number in the box above.

• Questions are equally weighted (but Q1 – Q2 which have 2 extra marks each). Special “Spring” treat: your lowest scoring answer won’t count.

• You have 40 minutes to answer all 17 questions.

1. On the right hand side, complete the concrete WHILE-program that is represented as

data on the left:

[[var,0],

[ [:=,[var,1],

[cons,[var,0],[quote,nil]]],

[while,[var,1],[]]

], [var,1]]

prog read X {

} write Y

2. For each tree in D tick ‘yes’ if it represents a list of numbers and write the corre- sponding list – e.g. [2,3] – in the provided space, or tick ‘no’ otherwise.

⟨nil.nil⟩

⟨nil.⟨⟨nil.nil⟩.nil⟩⟩ ⟨⟨⟨nil.nil⟩.nil⟩.⟨⟨nil.nil⟩.nil⟩⟩ ⟨nil.⟨nil.⟨⟨⟨nil.nil⟩.nil⟩.⟨nil.nil⟩⟩⟩⟩

yes yes yes yes

no no no no

3. Complete the sentence: “WHILE programs are a good choice for effective procedures because WHILE has just the right mix of

and .” [Neil Jones]

4. Complete the sentence: “The fact that we can compile TM programs to WHILE-

programs and vice versa, and WHILE-programs to SRAM programs and vice versa,

is evidence for thesis”.

5. Complete the definition of the operational semantics of the given RAM assignment:

p⊢(l,σ)→( ,σ[ ]) ifIl =

6. Complete the sentence: “The problem whether any given L-program p

is called the Halting Problem (for L). This problem is un .”

7. Complete: “To show that a problem A is undecidable it suffices to show that

is effectively reducible to .”

8. Which of the following problems are undecidable? Tick the ones that are.

Postman Parsing Tiling Halting Graph Colouring Primes

P.T.O

9. Which of the problems below can be shown to be undecidable (by Rice’s Theorem)? (a) A={d∈D|d=pandtimeWHILE(a)≤1,200,000foralla∈D}

p

decidable

undecidable by Rice’s theorem undecidable by other reason

(b) A={d∈D|d=pandpcompilesWHILEintoCM-programs} decidable

undecidable by Rice’s theorem undecidable by other reason

10. Complete the sentence: “ If E is a WHILE-expression, T E denotes

; for instance, T cons hd X nil evaluates to

11. Complete the definition:

C;S⊢time σ⇒t+t′ if C⊢time σ⇒t, C⊢ and S ⊢time

12. Define formally or informally (in any case precisely) the class LINL:

.”

.

.

13. True, false or unknown? Tick the boxes accordingly. The Postman problem is feasible

PGOTO = PTM

WHILE ≼lintime GOTO

true false true false true false true false

unknown unknown unknown unknown

There is an A ∈ EXP such that A ∈/ P

14. Fill in the gaps in the Linear Hierarchy Theorem: “There is a constant b such that

for a ≥ 1 there is a problem A in TIMEWH1LE(a×b×n)

that is not in .” 15. Assume we have a WHILE-program p such that timeWHILE(d) = 12|d|3 + 3|d| + 4.

Tick only the statements that are correct.

p∈TIMEWHILE(f)wheref(n)=n3+10n+10

p∈TIMEWHILE(O(n3 +n+6))

p∈TIMEWHILE(f)wheref(n)=9n2+512

p∈LINWHILE p∈PWHILE

p∈TIMEWHILE(O(n3))

16. Tick what is known to be true about the Travelling Salesman Problem. It is … inP inLIN inNP inOn×logn6 inO(n!×2n)

decidable undecidable semi-decidable

17. Let A ∈ NP and B ∈ NP. Is the concatenation of words from A and B, i.e. {w | w = st such that s ∈ A and t ∈ B}, also in NP? true false

Reason:

p

.