1.

a) Why is the D-Wave quantum processor cooled? Justify your answer.

b) At what temperature is the quantum processor cooled? How cold is this?

c) The D-Wave quantum computer is a probabilistic machine. How does this work? How can one mitigate wrong answers?

d) Is a probabilistic machine more like a DFA or an NFA? Justify your answer.

2

Let L = {M: M is a Turing machine that accepts at least two binary strings}.

a) Dene the notions of Turing-recognisable language and undecidable language.

b) Is L Turing-recognisable? Justify your answer with an informal argument.

c) Justify with a formal proof your answer to b).

d) Prove that L is undecidable. (Hint: use Rices theorem.)

3.

a) Dene the relation A m B.

b) Prove that if A m B, A m B, and B is Turing-recognisable, then A is decidable.