Assigned:
Wed 11 Feb 2004
Due:
Wed 18 Feb 2004 (This assignment cannot be accepted late!)
Note: This assignment cannot be accepted beyond its due date as I will distribute solutions at that time in preparation for the midterm exam.
Problem | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | ... |
---|---|---|---|---|---|---|---|---|---|---|
Credit | RC | RC | RC | EC | RC | RC | NA | RC | RC | ... |
where "RC" is "regular credit", "EC" is "extra credit", and "NA" is "not applicable" (not attempted). Failure to do so will result in an arbitrary set of problems being graded for regular credit, no problems being graded for extra credit, and a five percent penalty assessment.
Required: 5 of the following 6 problems
Points: 20 pts per problem
Hint: The use of multi-tape TMs and non-determinism may simplify your solutions.
Hint: For half of your proof, let y be an appropriate sequence of configurations.
Note: The material from Chapter 5 is not necessary to solve this problem.
Note: The material from Chapter 5 is not necessary to solve this problem.