Машина Тьюринга и алгоритмы Маркова. Машина Поста.

[ManInBlack]

Нужна помощь с записью данных ниже задач на бумаге В C++ с решением проблем нет, но как записать алгоритм на бумаге понятия не имею, надеюсь на вашу помощь.
Машина Поста:
На ленте машины Поста расположен массив из 2n ячеек. Составить программу по которой машина Поста, раздвинет на расстояние в одну ячейку две половины данного массива.
Машины Тьюринга и алгоритмы Маркова:
1) A={a,b,c}. За первым символом непустого слова Р вставить символ с.
2) A={a,b}. Для непустого слова Р определить, входит ли в него еще раз, его первый символ.

Заранее огромное спасибо.