Assigned:
Wed 05 Nov 2008
Due:
Wed 12 Nov 2008
Accepted without penalty until:
Fri 14 Nov 2008
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?