5CCS2FC2: Foundations of Computing II
Coursework 2
Issued: 7 December 2020 Deadline: 21 December 2020
Notice to Candidates:
This assessment is to be completed independently and submitted on KEATS by 18:00
on the date specified above. You should submit your solutions via the KEATS quiz
provided on the module page.
The assessment is ‘open book’ but you should complete your work independently.
Your work will be checked for plagiarism and collusion and discipliniary action will be
taken against any candidates caught colluding.
Please see the Plagiarism Declaration on KEATS.
Answer all parts of TWO out of THREE question (A, B, and C).
The total number of marks available for this assessment is 20 marks.
Question A
(i) Construct a recurrence relation for T (n), with T (1) = 1, such that
n2 log2(n) ≤ T (n) ≤ 3n2 log2(n) + 1 (†)
for all n ≥ 1. [3 marks]
(ii) Prove by induction on n that your recurrence relation satisfies either the upper bound or
lower bound provided in criteria (†). Note that if your recurrence relation involves floor
or ceiling functions then one bound will be easier to prove than the other.
Marks will be awarded for the clarity of your proof.
[7 marks]
Page 1 of 3
Question B
(i) Consider the following function M that returns True (resp. False) if the number of
iterations of the Collatz function required for the input string w, interpretted as a binary
integer, to reach 1 is < 100 (resp. ≥ 100).
def M(w) :
n = i n t (w, 2 )
k = 0
whi le True :
i f n==1: return ( k<100)
i f ( n%2)==0: n = n/2
e l s e : n = 3∗n + 1
k += 1
Construct a pair of functions M1(s) and M2(s) such that the language of M1 is equivalent
to the language of M2 if and only if M rejects the input word w = 1101.
Your construction must NOT require you to compute whether or not M rejects w.
You can make use of the function UTM(M,w) which simulates a Universal Turing Machine
and will return True (resp. False) if and only if M returns True (resp. False) on
input w.
[4 marks]
(ii) Given an (undisclosed) function reject(M,w) that takes two inputs: M an algorithm and
w an input String, and claims to return True if and only if M rejects the input word w.
Construct a function paradox(w) that takes a single String as input and outputs a
boolean True or False, such that
reject(paradox,paradox) = True ⇐⇒ paradox(paradox) = True
thereby proving that it is not possible for reject(M,w) to function as claimed, and
therefore that the Rejecting problem RTM is undecidable.
[4 marks]
(iii) What does this say about the decidability of the equivalence problem EQTM and why?
[2 marks]
Page 2 of 3
Question C
(i) Construct a Probabilistic Turing Machine (PTM) M and an input word w ∈ {0, 1}∗ that
has the following properties
— M has at least 5 states, including the initial, accepting and rejecting states,
— M has a non-terminating computation on your chosen input w,
— The expected termination time E [T ] of M on input w is finite.
[7 marks]
(ii) What is the probability of our proposed machine M accepting your proposed input
word w? i.e what is Prob (M(w) = 1)?
[3 marks]
End of Questions
Page 3 of 3

欢迎咨询51作业君