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.
computer science
Description
Last Name 3 digit : LAM
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.
