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

University of Sussex 4 May 2018

Feedback Limits of Computation Test – Dr Bernhard Reus

→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 {

while hd A {

B:= cons A nil ;

A:= tl A

} ]] } ,1] write B

Typical mistakes

[0,

[ [while,[hd,[var,0]],[

[:=,1,[cons,[var,0],[quote,nil]] ],

[:=,0,[tl,[var,0]]]

]

• Some students confused the answer with “self-referencing program”

• Some students wrote something about diagonalisation or decision procedures.

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⟩⟩

Typical mistakes

√yes [0] no

yes √yes √yes

√ no [1,0] no [0,1] no

• sometimes students have added an extra 0 to their lists, probably thinking the terminator (rightmost nil) is part of the list.

• The third case has sometimes been misidentified with [1,1] or wrongly consid- ered not to be a list of numbers.

3. Complete the sentence: “The WHILE language has just the right mix of

simplicity and expressive power (or expressivity) .” (Neil Jones)

Typical mistakes

• Most students got this right, some wrote “expressiveness” which was accepted.

• Some students wrote things like “self-expression” or “simplexity” and got marks for it but not full marks.

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

Typical mistakes

• Some students confused the answer with “self-referencing program”

• Some students wrote something about diagonalisation or decision procedures.

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

is undecidable by showing that B ≤rec A (B is effectively reducible to A) .”

Typical mistakes

• Many students confused the direction and wrote A ≤rec B (they got 4 marks though!)

• Some students (cleverly) wrote “by showing that A is equivalent to B” which was not the intended answer but cannot be faulted so they got full marks too.

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 the Church-Turing Thesis ”.

Typical mistakes

none.

7. What specific feature must a language offer such that we can write interpreters, compilers and specialisers in it? programs-as-data

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

• Many students got this right, but some ticked ⊥ or 4.

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

p⊢(l,σ)→( l+1 ,σ[ i := σ(σ(j))) ifIl=Xi:=

• Some students wrote l instead of l + 1 and some wrote illegible stuff.

• For the store update, many students wrote Xi instead of σ(i) and so on. • Some forgot about the extra σ( ) of the indirect addressing.

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

Typical mistakes

• All kinds of wrong guesses.

• For (a) the answer “decidable by Rice’s Theorem” got only one mark deducted because decidable is correct. But note that Rice’s Theorem cannot be used to show that a problem about programs is decidable

• For (b) the answer “undecidable by other reason ” got only one mark deducted because undecidable is correct.

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 = 1

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

(c) whileX{X:=tlX}⊢time {X:7}⇒(7×(1+(a)+(b))+1+(a))= 37 Typical mistakes

• (a) was answered correctly by most. A few wrote weird things like n or time.

• (b) was answered correctly by many. However, n – and variations thereof –

popped up more times now.

• (c) was done perfectly by very few. Many could not even say how often the loop was executed. This was the first factor before the ×. Many did not think of the time it takes to evaluate the card (every time!) and then +1 for checking whether it is nil or not.

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

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

Typical mistakes

p ∈ WHILElintime

p has a time bound in O(nlogn)

p∈PWHILE

• The correct two answers were ticked by many students.

• Many students ticked also n9 + 2 as time bound which is not the case for small

input.

• Also, still many students ticked the PWHILE answer, despite the fact that we mentioned often in lectures and exercises that this is a problem class (and not a program class).

13. Define formally or informally (in any case precisely) the class PWHILE: This is the class of problems decidable by a WHILE-program in polynomial time .

Typical mistakes

• Quite a large number of students confused this with the class of programs that run in polynomial time (3 marks for this).

• Some even wrote about a polynomial or linear time bound for the WHILE- language, though it’s not clear what that means even.

• Quote a number of students also did not care to answer this or wrote some fantasy text.

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

TIMEWH1LE(a × n) .” Typical mistakes

• Anumberofstudentschosenottoanswerthisbutquiteanumbergotitperfectly right.

• Some students just wrote TIMEWH1LE and got something for it.

• Some students just wrote a × n and got something for it.

• Some students wrote A in TIMEWH1LE(b × n) and got something for it.

15. Complete Cook’s thesis: “All ‘reasonable’ sequential notions of computa- tion can simulate each other up to polynomial time difference .”

Typical mistakes

• Quite a number of students confused this with the Church-Turing Thesis.

• Many students got at least “polynomial time (difference)” right (for 3 marks). The “sequential” was correctly given by only a few. “Non-parallel ” was accepted too.

• Note that up to “Ptime” is only not a clear answer (1 mark).

• All kinds of strange answers were given, also linear time was mentioned occa-

sionally.

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

Typical mistakes

• All kinds of wrong answers were given here.

√ true false unknown √ true false unknown √ true false unknown true false √ unknown true √ false unknown

• Very often “TSP is in P” was (wrongly) declared “true” or “false”.

• Very often “Complement of HALT is in EXP” was (wrongly) declared “un- known”. Note that the Halting Problem (and complement thereof) are not even decidable!

17. “IfAisinPandBisinP,thenA∩B(theintersectionofAandB)isinP”.

This statement is √ true false unknown (Tick one box.)

Explain your answer: (1) A ∩ B is decidable follows from A decidable and B

decidable running their decision procedures sequentially (2) It runs in polynomial time since the addition of two polynomials is a polynomial.

Typical mistakes

• This was a slightly difficult question.

• Most students ticked correctly ‘yes’.

• But nobody really gave a fully acceptable reason.

• Many students just wrote that this “must obviously” be the case. But it is not. One has to prove this.

• Many students confused “AisinP” with A is an element of problem P. But obviously A and B must be problems, and thus sets (otherwise the union would not make sense).