теория алгоритмов

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

2. Докажите, что множество A неразрешимо: A = { x ∈ ω : dom ϕx содержит не более x полных квадратов }.