Homework: Models of Computation
• Design a Turing machine that implements a queue. The input will be a string of the form {+x|-}, where x is a symbol in the input alphabet (other than + or -), e.g., "+a + b + c - +a + e - - + b". "+a" means add a to the tail of the queue, and - means remove the head of the queue. The output should be the contents of the queue after executing all the operations indicated by the input. In this example, the output would be "aeb". The TM should have three tapes, one for input, one for output, and a scratch tape. The scratch tape should have two tracks. You don't need to use Deus Ex Machina for this problem.
• Design and test a multi-tape Turing machine, M, that recognizes the language {ww|w ∈ Σ ∗} where Σ = {a, b}. Use Deus Ex Machina to create the TM.
• Complexity class P was defined with respect to single-tape Turing machines only (cf. Definition 1.11.) Suppose that language L is accepted in polynomially bounded time by some multi-tape Turing machine. Show that L is in P.
• Show that the language {wcwR|w ∈ Σ ∗} where Σ = {a, b} is in LOGSPACE by designing a multi-tape, off-line Turing machine that accepts it using only logarithmic space. (Hint: Your machine might use two worktapes to hold binary counters.)
• Use Deus Ex Machina to design a non-deterministic TM that accepts the language {a n|n is a composite number}. Recall that a number is composite if it is the product of two natural numbers other than 1. Use the Multiplication Machine as a submachine.
Format your homework according to the give formatting requirements:
a. The answer must be double spaced, typed, using Times New Roman font (size 12), with one-inch margins on all sides.
b. The response also includes a cover page containing the title of the homework, the course title, the student's name, and the date. The cover page is not included in the required page length.
c. Also include a reference page. The references and Citations should follow APA format. The reference page is not included in the required page length.