where i is such that |w i |= max(|w 1 |,|w 2 |,|w 3 |)if no two w’s have the same length,
and i = 0 otherwise.
5. Provide a ‘high-level’ description for Turing machines that accept the
following languages on {a, b}. For each problem, define a set of appropriate
macroinstructions that you feel are reasonably easy to implement. Then use
them for the solution.
(a)L = {ww R }.
(b)L = {w 1 w 2 :w 1 ≠w 2 :|w 1 | = |w 2 |}.
(c)The complement of the language in part (a).
(d)L = {a n b m :m = n 2 , ≥1}.
(e)L = {a n : n is a prime number}.
6. Suggest a method for representing rational numbers on a Turing machine,
then sketch a method for adding and subtracting such numbers.
7. Sketch the construction of a Turing machine that can perform the addition
and multiplication of positive integers x and y given in the usual decimal
notation.
8. Give an implementation of the macroinstruction
searchright (a, q i , q j ),
which indicates that the machine is to search its tape to the right of the current
position for the first occurrence of the symbol a. If an a is encountered
before a blank, the machine is to go into state q i , otherwise it is to go into
state q j .
9. Use the macroinstruction in the previous exercise to design a Turing machine
on Σ = {a,b}that accepts the language L (ab*ab*a).
10. Use the macroinstruction searchright in Exercise 8 to create a Turing
machine program that replaces the symbol immediately to the left of the
leftmost a by a blank. If the input contains no a, replace the rightmost
nonblank symbol by a b.
9.3 Turing's Thesis