Построить машину Тьюринга, применимую ко всем словам X1X2...Xn в алфавите {а, b} и переводящую их в слово α

Просто строй длинную ленту , что бы больше мест для пропусков имела

Для построения машины Тьюринга, преобразующей слова в алфавите {а, b} в слово α, можно использовать следующий алгоритм:

1. Поставить начальную точку чтения на самый правый символ слова.
2. Считать символ.
3. Записать его в ячейку памяти под текущим символом.
4. Сдвинуть позицию чтения на одну ячейку влево.
5. Повторить шаги 2-4 до тех пор, пока не будет достигнут начало слова.
6. Прочитать символ в начальной позиции.
7. Записать его в выходное слово α.
8. Сдвинуть позицию на одну ячейку вправо.
9. Повторить шаги 6-8 до тех пор, пока не будет достигнут конец слова.
10. Остановиться.

Таким образом, данная машина Тьюринга будет преобразовывать слова X1X2...Xn в алфавите {а, b} в слово α: XnXn-1..X1.