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. WhatisE􏰅consXX􏰆{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:=. P.T.O

10. Which of the problems below can be shown to be undecidable and why? Tick one box per question.
(a) A={d∈D|d=􏰁p􏰂andtimeWHILE(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=􏰁p􏰂andpisadecisionprocedureforPRIMEnumbers}
􏰀 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: