Построить машину Тьюринга, применимую ко всем словам x1x2 ....xn в алфавите {a, b} и переводящую их в слово ax1x2 ....xn-2b.

Машина начинает работу из стандартного состояния, т. е. обозревает ячейку с буквой x_n. Машина должна ее стереть, а также на n-1 месте оставить b или заменить a на b. Затем пройти все слово влево и вместо пустого символа написать a.

( переход в состояние q означает, что в нем машина обозревает x )