Construct a Turing machine that performs some elementary arithmetic. It decides the language C = {a^i b^j c^k | i x j = k and i, j, k >= 1}

First scan the string from left to right to verify that it is of form a+b +c +; if it is scan to start of tape* and if not, reject. Easy to do with finite control/FA.

2. Cross off the first a and scan until the first b occurs. Shuttle between bs and cs crossing off one of each until all bs are gone. If all cs have been crossed off and some bs remain, reject.

3. Restore** the crossed off bs and repeat step 2 if there are as remaining. If all as gone, check if all cs are crossed off; if so, accept; else reject.

* Some subtleties here. See book. Can use special symbol or backup until realize tape is stuck and hasnt actually moved left.

**How restore? Have a special cross-off symbol that incorporates the original symbol put an X thru the symbol