quiz | 代写oracle – COMPSCI 350 S1 EXAM

COMPSCI 350 S1 EXAM

quiz | 代写oracle – 该题目是一个常规的oracle的练习题目代写, 是有一定代表意义的oracle等代写方向, 该题目是值得借鉴的quiz代写的题目

数据库代写 代写oracle oracle代写

THE UNIVERSITY OF AUCKLAND

FIRST SEMESTER, 2020
Campus: City
COMPUTER SCIENCE
Mathematical Foundations of Computer Science
INSTRUCTIONS:
  • Attemptallquestions.
  • This exam will contribute 50% to your overall course mark.
  • To obtain full credit, your script must clearly explainwhyyour 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 ashttp: //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 isnt 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/.
  • Submit to Canvas/Exam Part 2 a TYPED pdf file containing YOUR LAST NAME, FIRST NAME(S), ID, followed, in order, by your solutions to Questions, B, C, D, E, F, G, H.

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 Universitys 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.

QUESTIONS

Part 1

Question A quiz in Canvas.

[40 marks]
Part 2
Question BFor everyx{ 0 , 1 }define the language
Setx={M|Mis a Turing machine which stops onx}.
(a) Give examples of Turing machinesMandMsuch thatM Set 101 andM 6Set 101.
Justify.
(b) Give examples of pairs(x,M),(x,M)such thatMSetxandM6Setx. Justify.
(c) Are there stringsx{ 0 , 1 }such thatSetxis finite? Justify.
(d) Can Rices Theorem be applied to the languageSet 101? Justify.
(e) Can Rices Theorem be applied to the languageSetxfor allx{ 0 , 1 }? Justify.
(f) IsSetxdecidable for allx{ 0 , 1 }? Justify.
(g) For everyx{ 0 , 1 },Setxcontains an infinite decidable subset. Justify.
[16 marks]

Question C (a) Prove that the complexity functionKcan be computed with an oracle forATM.

(b) Prove that there exists a constantc > 0 such that for all palindromesx { 0 , 1 }we have
K(x)
x
2
+c.
(c) Prove that there exists a constantc > 0 such that for all such that for allx{ 0 , 1 }we have
K(x)K(x) +cwherexis the complement ofx.
(d) Compare from three points of view the resultsC(b) and C(c).
[14 marks]

Question D (a) Draw the state diagram for a Turing MachineMthat 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 whichMaccepts, one whichMrejects, and one which causesMnot 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.

(d) There are an uncountable infinity of infinite strings over{ 0 , 1 }. For your answer toD(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]
Question ELetABbe the set of all elements that are contained in either bothAandB, or neitherAnorB.
(a) IfAandBare recognisable, isABrecognisable? Justify.
(b) IfAandBare decidable, isABdecidable? Justify.
[2 marks]
Question FConsider 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 thetransition 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]

Question GSuppose you have a Turing machineMthat recognises but does not decide a languageL. Assume you have a Turing machineHworking as follows:

H(M,w) =
{
1 , ifMstops onw,
0 , otherwise.
a) CanLbe decided usingH? b) Does it follow thatLis decidable? Justify your answers.
[3 marks]

Question HWe know thatAT Mis recognisable, but undecidable. Explain why this is a significant result in Computer Science. [4 marks]

END OF QUESTIONS