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作业君
