Машине Тьюринга и Машины Поста нужна помощь с решением

это тебе надо на каком языке программирования? Могу помочь на Pascal и C++

Помогаю:

Приступим к рассмотрению концепции, в пределах которой нужно решить задачи. Эта концепция называется абстрактной машиной Поста. Суть её проста: машина состоит из бесконечной ленты, разбитой на ячейки. И каретки, которая двигается вдоль ленты. Сама лента нас мало интересует, так как задачи решаются с помощью каретки. Я очень кратко расскажу о принципах работы этой машины. Кто хочет понять подробнее - "Google в помощь". Итак.

Меткой я буду называть любой символ, который находится на ленте. Обычно, под меткой подразумевается галочка или латинская буква "V". Массивом я буду называть метки на ленте, которые не разделены пустой ячейкой на той же ленте. Массивом я буду так же называть любое целое число: если это число 3, то, соответственно, где-то на ленте будут находиться три метки подряд. Пустую ячейку я буду именовать пробелом. Алгоритмом я буду именовать, собственно, способ решения задачи - комбинации действий, которые мы совершаем кареткой, которые нужно выполнить шаг за шагом, чтобы прийти к ответу. Под "ответом" я буду подразумевать определённое количество меток на ленте.

Рассмотрим, чем является "каретка":

Каретка может двигаться по ленте влево либо вправо, но только на одну ячейку за один шаг. Она может устанавливать либо удалять метку, но только, если в данной ячейке раньше либо не было метки, либо она присутствовала. Нельзя удалить пустоту и нельзя установить метку в ячейку, если она там уже установлена. И она (каретка) может проверять, находится ли в ячейке, над которой она остановилась, метка. Если метка присутствует, то мы можем перейти к какому-нибудь шагу алгоритма. Если метки нет в текущей ячейке - мы можем перейти на иной шаг алгоритма. Запомните главное: с помощью проверки можно организовать "круговорот действий" - цикл. Но недопустимо делать бесконечный цикл - алгоритм из действий каретки должен обязательно иметь конец, а каретка должна обязательно остановиться. Рассмотрим же, как это всё оформлять.

Мы можем говорить, чтобы каретка сдвинулась вправо вот так:
a) → b
Здесь и далее - "а" - номер шага в алгоритме. А "b" - номер шага алгоритма, к которому нужно потом перейти уже после (!) движения каретки вправо. Аналогично выполняется движение влево:
a) ← b
Установка метки:
а) V b
Удаление метки:
а) X b
Проверка на присутствие метки в ячейке, над которой остановилась каретка:
a) ?(a,b)
Тут нужно немного прояснить ситуацию: если метка в ячейке есть, то мы перейдём на шаг алгоритма под номером b. Если метки в ячейке нет, то мы перейдём на шаг алгоритма номер a. Помните: нельзя написать что-то вроде "?(a,a)" - это бесконечный цикл, из которого никогда не будет выхода, а программа обязана быть завершена с помощью такого простого оператора:
a) !
Операторов завершения программы может быть несколько на один алгоритм. Но нельзя после завершения программы перейти к выполнению другого шага: "! b" - ошибка.

Приведу пример алгоритма, включающего все действия. Будем считать, что на ленте не установлено ни единой метки:
1) → 2
2) ← 3
3) V 4
4) X 5
5) ?(6,3)
6) !

Легко увидеть, что с шага 5 мы никак не попадём на шаг 3, так как метка была удалена, а уже потом последовала проверка на присутствие метки. Следовательно, каретка, запрограммированная таким алгоритмом, будет выполнять ровно то, что мы написали. Нет ни бесконечных циклов, ни установки\удаления метки там, где она присутствует\отсутствует соответственно.