# CS代考计算机代写 University of Sussex 28 April 2017

University of Sussex 28 April 2017

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, write the program-as-data representation of the WHILE-

program on the left (variable numbers start at 0):

test read X { [ Y:= cons X X;

while X {

X:= tl X } }

write Y

]

2. Write the list below as element in D using only nils and ⟨ . ⟩-operations (linearly) [[0],[1]]

3. Complete: E cons E Fσ = .

4. Complete our definition of the Halting Problem below:

HALT = { [ p, d ] ∈ D | }

5. Complete the sentence: “For an L-program p, the term [p]L denotes the

of p which is a

function of type → .”

6. Every acceptable (i.e. reasonably expressive in a certain sense) programming language

automatically admits reflective programming. This is a consequence of

7. Complete the sentence: “ ‘Game of Life’ is a 2-dimensional automaton with four rules for: underpopulation, overcrowding, and .”

8. Complete: “To show that a problem A is decidable it suffices to show that is effectively reducible to

9. Which of the following problems are decidable? Tick the ones that are. TSP HALT Complement of HALT Matching Tiling

.

,

Primes P.T.O

.”

10. Which of the problems below can be shown to be undecidable (by Rice’s Theorem)? (a) A={d∈D|d=pandtimeWHILE(d)>|d| }

decidable

undecidable by Rice’s theorem undecidable by other reason

(b) A={d∈D|d=pandprunwithinputdisnotnil } decidable

undecidable by Rice’s theorem undecidable by other reason

11. Complete the following judgements about WHILE expressions and statements (n is a

natural number). No need to show your working unless outlined:

T tl X =

X := tl X ⊢time {X:n} ⇒ whileX{X:=tlX}⊢time {X:4}⇒

Tick only the statements that are correct. p ∈ WHILEtime(f ) where f (n) = n3 + 456

phasatimeboundinO(n3) p∈PWHILE

13. Complete: L1 ≼linear−pg−ind L2 means that

14. Complete Cook’s thesis: “Computability

is equivalent for all (reasonable)

of computation.”

15. True, false or unknown? Tick the boxes accordingly.

TIMEWHILE(n) TIMEWHILE(n · log n) There are no problems that aren’t in NP 0-1 Knapsack is in P

WHILE ≼ptime TM ThereisanA∈EXPsuchthatA∈/P

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

p

× +

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

times loop body is executed

p

p ∈ WHILElintime

phasatimeboundinO(n5)

f(n)=n3 +16n2 isatimeboundforp

.

16. Complete: “Robustness” of P refers to the fact that decidability of problems in is independent of

.

17. Complete: “It is difficult to show that a problem is not in P. Currently, the closest

to “TSP is not in P” that one can actually prove is “TSP is

” under the assumption P NP.