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

[arseniiv]

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

это $\wedge$

Хм. Для любой строки $\wedge a = a \wedge = a$. Вы правильно понимаете, что такое пустая строка?

Приведу первое и последнее правила возможного решения:
$1 \to aab, \ldots, b \mathrel{\to\!\cdot} \wedge$. Немного не так, но примерно так.

Хм, решение не представляется таким простым, как раньше.

[Nemiroff]

Цитата:

Немного не так, но примерно так.

А что этот алгоритм остановится, вы уверены? Просто перегон $a\to 1$ запускает первое правило, а как вы это обойдете, я не понял.

[arseniiv]

Nemiroff в сообщении #510182 писал(а):

Просто перегон $a\to 1$ запускает первое правило, а как вы это обойдете, я не понял.

Перегонять только в контексте $b$, а $b$ при этом сдвигать. Перед этим процессом надо избавиться от всех $b$ кроме правого. Только проблемы с приоритетом правил получились.

[Nemiroff]

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

Перегонять только в контексте $b$, а $b$ при этом сдвигать. Перед этим процессом надо избавиться от всех $b$ кроме правого. Только проблемы с приоритетом правил получились.

Ввод разделителя надо делать последним правилом, чтоб он выполнялся только однажды.

(Оффтоп)

Я бы решил, что нечто такое:
$,1\to11,$ $,\to\cdot$ $1\to,1$

[arseniiv]

(Оффтоп)

$111 \to ,111 \to 11,11 \to|$.

[_hum_]

Народ, вы о чем, какие разделители, какие пустые строки. Достаточно ведь

(Оффтоп)

$\mathbb{A} = \{|, \triangle\}$ и продукций:
1) $| \rightarrow \triangle \triangle $
2) $\triangle \rightarrow |$

[arseniiv]

_hum_, $| \to \triangle\triangle \to |\triangle \to \triangle\triangle\triangle \to |\triangle\triangle\triangle \to \ldots$

[_hum_]

Да, согласен.

[Nemiroff]

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

(Оффтоп)

$111 \to ,111 \to 11,11 \to|$.

Это что?
Если это контрпример моему алгоритму, то там последний шаг неверен. Выполнится снова первое правило.

[arseniiv]

Ой, точно!

Волшебный алгоритм!

[Sverest]

Nemiroff в сообщении #510186 писал(а):

Я бы решил, что нечто такое:
$,1\to11,$ $,\to\cdot$ $1\to,1$

Может нужен такой шаг $,1\to.11$

[arseniiv]

Не нужен. Всё работает. Вы проверьте! Прямо здесь прогоните строку, например, $111$.

[Sverest]

Шаг $,1 \to 11,$

$,111, \to ,11,11$
Опять зацикливание

[Nemiroff]

Мда.
$111\to,111\to11,11\to1111,1\to111111,\to111111$

[_hum_]

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