CS5034 Homework Assignment 13

Posted: November 20, 1997 Due: December 11, 1997 at 5:00

This assignment is worth a total of 70 points. This homework is subject to the CS5034 General Rules for Homework Submission (see the web site). Be sure to include your name(s) and ID number(s) with your submission. Send homework submissions email to cs5034@ei.cs.vt.edu. Your email message should contain ONLY the Postscript file for your homework submission - preferably as an attachment- and should have a suitable subject line such as ``HW 11 SUBMISSION.'' The email account will automatically reply when a message is received.

Answers to questions should be correct, clear and concise. Solutions will be marked down if they contain extraneous material; gaps, inconsistencies or illogical connections in proofs or explanations; or incorrect results. Be sure to explain all answers. Good, clear English is required. NOTE: The answer to each question (except the last) is limited to one page. All parts to multi-part questions must fit within the one page limit.

Where an exercise number is referenced, the question is from Hein. Each question is worth 10 points, except the last which is worth 20 points.

1. Exercise 13.2.3 parts b and d.

2. Exercise 13.2.7 parts b and d.

3. Exercise 14.1.4 parts b and d.

4. Exercise 14.3.11 parts b and d.

5. Exercise 14.3.18 parts b, d, and f.

6. Which of the following problems about Turing machines are solvable, and which are unsolvable? Explain your answer carefully.

(a)

To determine, given a Turing machine M, a state q, and a string w, whether M ever reaches state q when started with input w from its initial state.

(b)

To determine, given a Turing machine M and a string w, whether M ever moves its head to the left when started with input w.

(c)

To determine, given two Turing machines, whether one accepts the complement of the language accepted by the other.

(d)

To determine, given two Turing machines, whether there is any string on which each halts.

(e)

To determine, given a Turing machine M, whether the language accepted by M is finite.