THE UNIVERSITY OF AUCKLAND
FIRST SEMESTER, 2020 Campus: City
COMPUTER SCIENCE Mathematical Foundations of Computer Science
INSTRUCTIONS:
• Duration:29June13.00NZT–30June12.59NZTsubmittedinCanvas
• Attempt all questions.
• This exam will contribute 50% to your overall course mark.
• To obtain full credit, your script must clearly explain why your answers are correct.
• You can use without proof any result proved in class. You need to state correctly the
result and show how it applies to the specific problem you solve.
• For state diagrams, we would prefer that you use a state designer such as http: //madebyevan.com/fsm/, which generates both images and LATEX code. Your images can be hand-drawn and scanned, if necessary. No other handwriting will be marked.
• Your submissions are expected to adhere to the Academic Integrity standards. You cannot submit any material for assessment that isn’t your own work. The Proof Styles video provides tips for writing proofs building on, but not copying, course material.
• Answer Question A in Canvas/Quizzes/.
• SubmittoCanvas/ExamPart2aTYPEDpdffilecontainingYOURLASTNAME,
FIRST NAME(S), ID, followed, in order, by your solutions to Questions, B, C, D, E, F, G, H.
COMPSCI 350 S1 EXAM
CONTINUED
QUESTION SHEET 2 COMPSCI 350 S1 EXAM
By completing this assessment, I agree to the following declaration:
I understand the University expects all students to complete coursework with integrity and honesty. I promise to complete all online assessment with the same academic integrity standards and values. Any identified form of poor academic practice or academic misconduct will be followed up and may result in disciplinary action. As a member of the University’s student body, I will complete this assessment in a fair, honest, responsible and trustworthy manner. This means that: I declare that this assessment is my own work, except where acknowledged appropriately (e.g., use of referencing).
I will not seek out any unauthorised help (i.e., anyone other than the course lecturer or tutor) in completing this assessment.
I declare that this work has not been submitted for academic credit in another University of Auckland course, or elsewhere.
I am aware the University of Auckland may use Turnitin or any other plagiarism detecting methods to check my content.
I will not discuss the content of the assessment with anyone else in any form, including, Canvas, Piazza, Facebook, Twitter or any other social media within the assessment period.
I will not reproduce the content of this assessment anywhere in any form.
CONTINUED
Question C
Question D
(a) Give examples of Turing machines M and M′ such that ⟨M⟩ ∈ Set101 and ⟨M′⟩ ̸∈ Set101. Justify.
(b) Giveexamplesofpairs(x,M),(x′,M′)suchthat⟨M⟩∈Setx and⟨M′⟩̸∈Setx′.Justify. (c) Are there strings x ∈ {0, 1}∗ such that Setx is finite? Justify.
(d) Can Rice’s Theorem be applied to the language Set101? Justify.
(e) Can Rice’s Theorem be applied to the language Setx for all x ∈ {0, 1}∗ ? Justify.
(f) IsSetx decidableforallx∈{0,1}∗?Justify.
(g) For every x ∈ {0, 1}∗ , Setx contains an infinite decidable subset. Justify.
[16 marks]
(a) Prove that the complexity function K can be computed with an oracle for ATM.
(b) Prove that there exists a constant c > 0 such that for all palindromes x ∈ {0, 1}∗ we have
K (x) ≤ x + c. 2
(c) Prove that there exists a constant c > 0 such that for all such that for all x ∈ {0, 1}∗ we have K(x) ≤ K(x) + c where x is the complement of x.
(d) Compare from three points of view the results C(b) and C(c).
[14 marks]
(a) Draw the state diagram for a Turing Machine M that accepts an infinite number of strings in {0,1}∗, rejects an infinite number of strings in {0,1}∗, and does not halt on an infinite number of strings in {0, 1}∗.
(b) Provide configuration sequences for 101 and two other strings of at least 3 symbols length, one which M accepts, one which M rejects, and one which causes M not to halt.
(c) Draw the state diagram for a standard Turing Machine that, for every possible prefix, accepts an infinite number of strings, rejects an infinite number of strings, and does not halt on an infinite number of strings. Minimise the number of states that you use. Hint: Think about modulo 3.
CONTINUED
QUESTION SHEET
3 COMPSCI 350 S1 EXAM
Part 1
Question A Quiz in Canvas.
Part 2
[40 marks]
Question B For every x ∈ {0, 1}∗ define the language
Setx = {⟨M ⟩ | M is a Turing machine which stops on x}.
QUESTIONS
Question E
Question F
Question G
Question H
(d) There are an uncountable infinity of infinite strings over {0,1}∗. For your answer to D(a), state how many strings are accepted (countably or uncountably infinite); how many strings are rejected; and how many strings the Turing machine does not halt on. Explain your answers.
[15 marks]
Let A ⊗ B be the set of all elements that are contained in either both A and B, or neither A nor B. (a) If A and B are recognisable, is A ⊗ B recognisable? Justify.
(b) If A and B are decidable, is A ⊗ B decidable? Justify.
[2 marks]
Consider the following variant of a Turing machine. In addition to moving Right or Left along the tape, the Turing machine has a third option: Splitting the current cell. This option divides the current cell into two cells, with the left-hand cell containing what was contained in the original cell, while the right-hand cell contains the output specified by the δ transition function. The tape head moves to the right-hand cell. Is this new Splitting Turing machine equivalent in power to a standard Turing machine? Give reasons for your view (this need not be a formal proof, although formality is preferred).
[6 marks]
Suppose you have a Turing machine M that recognises but does not decide a language L. Assume you have a Turing machine H working as follows:
1, ifMstopsonw, H(⟨M⟩,w) = 0, otherwise.
a) Can L be decided using H? b) Does it follow that L is decidable? Justify your answers.
[3 marks]
We know that AT M is recognisable, but undecidable. Explain why this is a significant result in Computer Science.
QUESTION SHEET 4 COMPSCI 350 S1 EXAM
END OF QUESTIONS
[4 marks]