Explaining Computation of a Turing Machine

Question

I am having some trouble interpreting what this Turing machine actually does (i.e., I am uncertain how to explain it in plain English).

I believe I have created the state diagram correctly using the transition table I was given (although not 100% on this either).

From what I can see this TM will halt in an accepting state (q2) whenever the input is of the form

(a || b || B)*Ba*c(a || b || c || B)*,

that is any amount of a's, b's, and blanks (but no c's), followed by at least one blank, any amount of a's, and exactly one c. Anything can come after since we go left upon finding first c.

I suppose my question is

a) Is my work up to this point correct? and

b) Is there a more meaningful explanation of this Turing machine (i.e. a richer description than I wrote of the input that halts in (q2)).

Answer 1

Some observations:

1. q0 reads left to right, doesn't change the tape, and stops when it hits c.
2. q1 reads left to right, swaps a and b, halts when it sees a B and turns around when it hits an a.
3. The only way to for the TM to halt is if
   • There is a c somewhere on the tape to the right of the initial tape position
   • In q1, the last pass from right to left sees only b and leaves only a between the first c and the rightmost B to the left of c.
4. q1 changes everything between the first c and the rightmost b to the left of that c to a b eventually

Given initial tape configuration >BxBycz, the machine will always halt in configuration >BxB(a^|y|)cz. It accepts any string that contains c.

Your state diagram disagrees with the table in that the table has the transition function defined so that f(q1, a) = (q0, b, L) and f(q1, b) = (q1, a, L), but your diagram shows f(q1, a) = (q1, a, L) and f(q1, b) = (q0, b, L).