Create Turing machines to solve the following problems. For each problem, begin by stating a high-level plan ("scan right changing all 'a's into 'x's, in order to "). See Sipser examples. Further components:

TM diagram with diagram legend.

Three or more good strings and three or more bad strings (for string recognition problems), or four or more different input data values (for example, on "add two unary numbers," four different addition problems). Each must have its own distinct description ("adding equal values"). Run every test case carefully, including those included here.

A statement of any assumptions and limitations particular to your TM (but these can't change or eliminate any specifications).

No formal definition.

a) Copy a non-empty input string. The original string remains on the tape, unchanged, followed by the an 'x', followed by the copy; any working space is cleared. Do not reset the head. State what would happen with your particular machine if the specification that the string is non-empty were removed; be specific, including what state the machine will terminate in. = {0, 1}

b) Reverse a string using the same specifications as part a.

c) Remove adjacent duplicates in a non-empty string; remember to test cases of more than two equal adjacent values (i.e., yyyy ). The final tape has only the updated string. You may choose to have an initial $ marker or not (i.e., you don't need to create it, you may just assume it is part of the given input). State which you have and why. Reset the head. = {x, y}