@Bonab

A={ | }. Считая слово P записью числа в единичной системе, определить, является ли это число степенью 3 (1, 3, 9, 27, …). Ответ: пустое слово, если является, или слово из одной палочки иначе.
сделайте в машине тьюринга, а то мой мозг скоро отрафируется, я скажем по мягче "устал от этого"

0

@Sindbad_M

делить строку на три до тех пор пока в частном не останется единица. Если на каком-либо шаге деления появился не равный нулю остаток - значит не степень. Если дошли до единицы в частном - степень.

0

@Bonab

Sindbad_M, ничего не понятно

0

@Sindbad_M

Алгоритм деления на три
1. Перемещаете головку на первый (левый) символ исходного слова (или того, что от него осталось)
2. Стираете первый символ, перемещаетесь вправо
3. Если это пустая ячейка, то перейти на п. Х1
4. Стираете второй символ, перемещаетесь вправо
5. Если это пустая ячейка, то перейти на п. Х2
6. Стираете третий символ, перемещаетесь вправо
7. Если это пустая ячейка, то перейти на п. У
8. Перемещаете головку на последний символ исходного слова
9. Перемещаете головку на две ячейки вправо
10. Перемещаете головку вправо до первой пустой ячейки (при первом проходе алгоритма, мы уже стоим на этой самой пустой ячейке)
11. Ставите символ "|" и переходите на п.1


В результате мы постепенно, тройками, стираем начальное слово (делимое), для каждой тройки ставим одну палочку в новом слове, которое формируем через пробел правее исходного (это частное).

Указанный выше алгоритм может завершиться в трех случаях

Х1 - остаток от деления на три равен одному. Нужно проверить частное, если оно равно нулю, то слово является степенью трех, в противном случае - не является

Х2 - остаток от деления на три равен двум. Слово не является степенью трех.

У - остаток от деления на три равен нулю. Нужно принять получившееся частное за исходное слово и применить к нему алгоритм деления с самого начала.

1