COSC1107 Computing Theory Assignment

COSC1107/1105 - Computing Theory Assignment 2 (15%)

Total marks: 90 (15% whole course)

Please read all the following information before attempting your assignment. This is an individual assignment. You may not collude with any other individual, or plagiarise their work. Students are expected to present the results of their own thinking and writing. Never copy another student’s work (even if they “explain it to you first") and never give your written work to others. Keep any conversation high-level and never show your solution to others. Never copy from the web or any other resource. Remember you are meant to generate the solution to the questions by yourself. Suspected collusion or plagiarism will be dealt with according to RMIT policy.

Submission Instructions

You are to submit a PDF file and one zip file named with your student number (e.g., 3451234.zip) containing (in its root folder) your three .jff files for exercise 1 via the following Google Form:

http://tinyurl.com/ct19-ass2-sub

The PDF file can have any name as long its extension is .pdf, but it must must be typeset in a word processor (scanned files will not be marked) and have your student name and number on it. Python validator scripts for the zip file can be obtained here. The three JFLAP files must follow the exact name conventions as specified below in each question, and must load & run in JFLAP 7.0 with no errors whatsoever in reasonable amount of time (see below).

In the submission form you will be required to certify that the submitted solution represents your own work only by agreeing to the following statement:

I certify that this is all my own original work. If I took any parts from elsewhere, then they were nonessential parts of the assignment, and they are clearly attributed in my submission. I will show I agree to this honor code by typing "Yes":

If you are not able to certify this, it is best not to submit anything. Submissions not compatible with the instructions above will attract zero marks and do not warrant a re-submission.

Corrections: From time to time, students or staff find errors (e.g., typos, wrong/missing symbols, ambiguous text) in the assignment specification. In that case, a corrected version will be uploaded to the course web page as quickly as possible, an announcement will be made on the course web page as well as in the forum. Check the version on the bottom left.

Forum postings on assignment: Never post any information on the forum that may disclose how to solve a question or what the solution may be. You may only post assignment related questions for clarification, for example, to clarify certain notation. Any post discussing possible solutions or strategies may directly be considered plagiarism, see above. If in doubt, do not post and ask us the question instead.

Silence Policy: A silence policy will take effect 48hrs before this assignment is due. This means no questions about this assignment will be answered, whether they are asked on the discussion board, by email, or in person.

Late Submissions/Extensions: A penalty of 10% per day is applied to late submissions up to 5 days, after which you will lose ALL the assignment marks. Extensions will be given only in exceptional cases; please refer to Special Consideration process. Special Considerations given after solutions have been released (between 1 and 2 weeks after deadline) will automatically result in an equivalent assessment in the form of a test, assessing the same knowledge and skills of the assignment (location and time to be arranged by the instructor).

Exercise 1: Undecidability Exercise 2: Undecidability. . . . . . . . . . . . . . . . . . . . . . . . . 20 marks

Let L₁ = {M | M is a TM that halts on the empty tape leaving exactly two words on its tape in the form Bw₁Bw₂B}.

1. (15 marks) You have seen the proof in tutorial 7 (PART 2) that A_TM, the problem of deciding whether an arbitrary Turing machine will accept an arbitrary input, is undecidable. Use this result to prove, formally using problem reduction, that given an arbitrary Turing machine M, the problem of deciding if M ? L₁ is undecidable.
2. (5 marks) Is L₁ recursive, recursively enumerable, non-recursively enumerable, uncomputable? Justify your answer.

Exercise 2: Complexity

Exercise 3: Complexity. . . . . . . .25 marks

1. (6 marks) Prove mathematically that if a Turing Machine runs in time O(g(n)), then it runs in time O(h(g(n))+c), for any constant c = 0 and any functions g(n) and h(n) where h(n) = n.
2. (14 marks) A cutting-edge publisher based in Melbourne is publishing a book on complexity theory. They learnt that you are taking Computing Theory at RMIT, so they offered you a very well paid job! For the job, you are asked to write the part of the book that explains the following picture:

Your text will go to a proper book, so it has to be professional, well written, and clear. And of course, you are to explain the figure the best way possible! The publisher told you that you can use no more than one page.

3. (5 marks) Consider the following problem SC: “given a set of elements U = {u₁,u₂,...,u_n} and a set S of subsets of U (i.e., S ? 2^U) where ^[ s = U, find the smallest set C ? S such that ^[ c = U?”

s?Sc?C

The SC problem is a very famous one, and one much studied. Explain why stating that SC is the NP-complete complexity class (or SC is an NP-complete problem) would be technically incorrect to say. Note: A perfect answer can be stated in no more than 3 short sentences.

4. (5 points (bonus)) In no more than half a page, explain and discuss the the phase transition phenomenon in random Random 3-SAT. Note: This requires some research. Marks will depend on quality of presentation, and depth and breath of the explanation.