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 = := Xj.
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=􏰁p􏰂andtimeWHILE(a)≤1,200,000foralla∈D}
p
􏰀 decidable
􏰀 undecidable by Rice’s theorem 􏰀 undecidable by other reason
(b) A={d∈D|d=􏰁p􏰂andpcompilesWHILEintoCM-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 􏰀inO􏰃n×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
.