# CS代考计算机代写 interpreter University of Sussex 4 May 2018

University of Sussex 4 May 2018

Limits of Computation Test

→a→→→→→→→→→ → → 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, write the program-as-data representation of the WHILE- program on the left (variable numbers start at 0):

test read A { [0,

while hd A {

B:= cons A nil ;

A:= tl A

} }

write B

]

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

⟨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: “The WHILE language has just the right mix of

and .” (Neil Jones)

4. Complete: “To show that HALT is WHILE semi-decidable we programmed a

in WHILE.

5. Complete: “If problem B is known to be undecidable we can show also that problem A is undecidable by showing that .”

6. 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 ”.

7. What specific feature must a language offer such that we can write interpreters, com- pilers and specialisers in it?

8. WhatisEconsXX{X:2}? ⟨nil.nil⟩ ⟨2.2⟩ ⊥ 4 4

9. Complete the definition of the operational semantics of a specific RAM assignment:

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

10. Which of the problems below can be shown to be undecidable and why? Tick one box per question.

(a) A={d∈D|d=pandtimeWHILE(d)≤10×|d|3 } p

decidable by giving decision procedure decidable by Rice’s Theorem undecidable by Rice’s theorem undecidable by other reason

(b) A={d∈D|d=pandpisadecisionprocedureforPRIMEnumbers}

decidable by giving decision procedure decidable by Rice’s Theorem undecidable by Rice’s theorem undecidable by other reason

11. Complete the following judgements about WHILE expressions and statements (n is a natural number) making correct use of the already given arithmetic operations. Use (a) in (b) and (a),(b) in (c).

(a) T X =

(b) X:=tlX⊢time {X:n}⇒ +

)+ )= 12. Assume we have a WHILE-program p such that timeWHILE(d) = 2|d|2 + 2|d| + 1.

+

(c) whileX{X:=tlX}⊢time {X:7}⇒( ×( + +

=

Tick all statements that are correct.

p ∈ WHILEtime(f) where f(n) = n3 + 56 p has a time bound in O(n2)

f(n)=n9 +2isatimeboundforp

p

p ∈ WHILElintime

p has a time bound in O(nlogn)

p∈PWHILE

13. Define formally or informally (in any case precisely) the class PWHILE:

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

that for all a ≥ 1 there is a problem A in TIMEWH1LE(a×b×n) that is not in .”

15. Complete Cook’s thesis: “All ‘reasonable’ notions of computation can simulate each other up to

16. Are the following statements true, false or unknown? Tick one box per statement.

.”

Parsing is in P PRAM = PTM

WHILE ≼lintime GOTO

Travelling Salesman Problem is in P Complement of HALT is in EXP

true false unknown true false unknown true false unknown true false unknown true false unknown

17. “IfAisinPandBisinP,thenA∩B(theintersectionofAandB)isinP”. This statement is true false unknown (Tick one box.)

Explain your answer: