Здравствуйте

1. Постройте машину Тьюринга для следующей задачи. На вход подаётся слово w в алфавите
{ a, b }. Нужно вставить символ b после каждого блока символов a нечётной длины. Например,
если w = aabbaaabaabbbaaa, то результатом будет w = aabbaaabbaabbbaaab. Разбейте программу
на логические части и прокомментируйте каждую из них.
2. Докажите, что множество A неразрешимо:
A = { x ? ? : dom ?x содержит не более x полных квадратов }.