Нормальный алгоритм для вычисления функции f(x) = 2x

[Sverest]

Построить нормальный алгоритм в алфавите $A=\{1\}$, вычисляющий функцию $f(x)=2x$

С чего надо начать?
Как я понял надо увеличить каждую единицу в два раза: то есть было - 1, а станет - 11, так?

[Mega Sirius12]

Написать построение функции на русском языке, а потом закодировать слова палочками
(КО)

[Zipfolder]

Нужно ещё как-то отделять «удвоенные» единицы от ещё не обработанных.

[Sverest]

$1 \to 11, \wedge \to .\wedge$

[Joker_vD]

А он разве остановится?

[arseniiv]

(Оффтоп)

А что означает $\wedge$?

[Sverest]

arseniiv в сообщении #510140 писал(а):

(Оффтоп)

А что означает $\wedge$?

(Оффтоп)

Пустой символ

-- Ср ноя 30, 2011 18:34:20 --

Joker_vD в сообщении #510138 писал(а):

А он разве остановится?

нужно как то сделать счетчик который подсчитает количество единиц, но только как?

[arseniiv]

(Оффтоп)

Sverest в сообщении #510144 писал(а):

Пустой символ

(Пустую строку тогда уж.) Спасибо.

Sverest в сообщении #510144 писал(а):

нужно как то сделать счетчик который подсчитает количество единиц, но только как?

Счётчик не нужен, используйте контекст. Ничто не мешает сначала все единицы превратить во что-нибудь другое.

[Sverest]

arseniiv в сообщении #510152 писал(а):

Ничто не мешает сначала все единицы превратить во что-нибудь другое

Но ведь надо использовать алфавит $A=\{1\}$

[arseniiv]

Ну так желаю вам удачи тогда. Если входное и выходное слово должны быть из $A^*$, это, наверно, не значит, что промежуточные там должны быть.

[Sverest]

arseniiv в сообщении #510158 писал(а):

Ну так желаю вам удачи тогда. Если входное и выходное слово должны быть из $A^*$, это, наверно, не значит, что промежуточные там должны быть.

$1 \to k,~ k \to 11,~ 01 \to \cdot 01$

тогда вот так можно?

[Nemiroff]

Цитата:

тогда вот так можно?

Он не остановится.

[arseniiv]

Ноль откуда?

[Sverest]

arseniiv в сообщении #510165 писал(а):

Ноль откуда?

это $\wedge$

[Nemiroff]

У вас нет такого символа. А строка используется в отдельном правиле, а не совместно с символами алфавита.
Ваш алгоритм не остановится - у него первое и второе правила вызывают друг друга.