Assigned:
Wed 04 Nov 2009
Due:
Wed 11 Nov 2009
Accepted without penalty until:
Fri 13 Nov 2009
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: 3 of the following 4 problems
Points: 30 pts per problem
Hint: For part (a), show that 2-PDAs can simulate Turing Machines, and for part (b), show that Turing Machines can simulate 3-PDAs. (For the latter part, you will likely need multi-tape Turing Machines, which can themselves be simulated by ordinary Turing Machines.)
Hint: You may use multi-tape Turing Machines which we have proven to be equivalent in power to ordinary Turing Machines.
Hint: You may use multi-tape Turing Machines which we have proven to be equivalent in power to ordinary Turing Machines. Non-determinism may also come in handy.
Hint: Let X be the ordered set {a, d, k, z}. Then one can denote the subset Y = {a, k, z} by the sequence 1011; each "1" indicating that the corresponding element from the original set is present in the subset, and each "0" indicating that the corresponding element is absent.
How do you think that |22N| and |2N| compare? How many "levels" of infinity do you think that there are?