Машина Тьюринга для f(x)=2x+1

[sergeysleep]

Алфавит: $\{1,\Lambda\}$
$f(x)=2x+1$
Пусть $x=m$, его код: $1^{m+1}$
В итоге должны получить:
$f(m)=2m+1$, его код: $1^{2m+2}$

То есть нужно продублировать на ленте каждую единицу.
Только вот как это сделать - понятия не имею

[nikvic]

для такого алфавита удобно считать, что состояние помнит состояние нескольких последних посещённых ячеек.
Придётся "работать" с двумя группами единиц. Уничтожать с правого конца первой группы по палочке, бежать направо и в конце добавлять пару палок. Или в правой группе добавлять одну палку слева (место есть), одну - справа.
Для начала бежать направо и ставить палку за первой свободной ячейкой (т.е. организовать запись числа ноль).

[Dosaev]

На 2-ленточной влет делается...