Привет, доброанон.

Рассмотрим машину Тьюрингу, которая за один такт работы может в текущей ячейке изменить символ, затем изменить состояние и сдвинуться влево-вправо (или остаться на месте).

Рассмотрим ленту, на которой могут быть только символы "1" и "0". Пусть "0" - это пустая ячейка. Имеем унарную СС, в которой 1 = "1", 2 = "11", 3 = "111" ну и т.д.

А теперь - суть задания. На ленте есть некоторой натуральное число в этой унарной СС. Нужно умножить это число на 3. Пример: исходная лента "11", выходная лента "111111".

Анон, подай мне идею, пожалуйста, как можно это сделать.