|
| Homework 9General Comments
- Problems are taken from the textbook unless otherwise noted.
- For full credit, provide context for each problem, show all calculations, and explain your work/answers.
- Numbers and/or algebra by themselves are not enough.
- You will lose a significant amount of credit if you do not show enough work/context for your answers.
- Precision is very important. You cannot skip steps, make guesses, or use flawed logic. Any of these things can lead to incorrect answers.
- Homework assignments must be very neatly written or typeset
(e.g. using Word or OpenOffice).
- You must indicate any assistance you had on an assignment as specified on the Policies page.
Details| Problem | Points | Hints
|
|---|
| 3.8b | 5 | Read the solution to part a. Your answer should be in the same form.
| | 3.8c | 5 | This one is easy if you simply make the appropriate modifications to your solution to part b. In fact, you can phrase your answer by describing how to modify your answer to part b. Alternatively, you can use your TM from part b in your TM for this problem.
| | 3.12 | 5 | Show how to simulate a regular TM with a Turing machine with left reset. Be very precise in your description and carefully read your answer to ensure that it contains all of the necessary details.
| | 3.15b | 5 | Read the solution to part a. Your solution should be similar in that you need to describe a TM based on one or two other TMs. Make sure you include all of the details that the given solution contains to ensure full credit.
| | 3.15d | 5 | See comment for previous problem.
| | Problem in Hint--> | 5 | Explain why your construction for 3.15d does not work for Turing-recognizable languages.
|
General Hints:
Remember that a TM is not guaranteed to
halt unless it is a decider and
that a decider always needs to halt.
|
|
|