6) (30 points) Give the state
machine and algorithm description of a Turing machine that accepts strings
in PALINDROME with a #
in the middle of the string. The alphabet for this language should be the first 2 distinct letters of your last name.
7) (10 points) Explain why non-determinism has no effect on computability. Your answer should include the effect of non-determinism on both the set of regular languages and the set of Turing-recognizable languages.
8) (10 points) Explain how the Universal Turing Machine “bridges the gap” between a state machine that accepts a set of strings to a model for general computing. Hint: von Neumann extended the idea.
Bonus: (2 points) Give two examples of how the material in CMPS 479 can be used in the real world.