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

[Sverest]

_hum_ в сообщении #510235 писал(а):

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

То есть это сделать нельзя?

[Nemiroff]

Цитата:

Но тогда эта же продукция окажется применима и к гипотетическому окончательному результату - а значит, это результат не будет результатом - алгорифм не остановится.

То, что она применима, не значит, что она произойдет. Алгоритм Маркова допускает принудительный останов командой $\to\cdot$
Я же уже привел решение, что еще надо?

[_hum_]

Ну, если считается, что алгорифм может принудительно останавливаться, тогда, конечно, утверждение не верно.

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

[Sverest]

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

[Nemiroff]

Sverest, нет у вас никакого нуля. И поэтому первое правило будет выполняться вечно.
_hum_, полагаю, это важно. Машину Тьюринга ведь можно принудительно останавливать.

[_hum_]

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

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

Вот тут проверьте: http://cmcmsu.no-ip.info/1course/alg.schema.nam.htm

2Nemiroff
Да, но, например, рекурсивные функции никто не останавливает, а тем не менее они прекрасно справляются с полнотой ;)

[Nemiroff]

Цитата:

Вот тут проверьте: http://cmcmsu.no-ip.info/1course/alg.schema.nam.htm

Там в примерах такая задача есть.
Только я не уверен, что корректно вводить пустую строку в правило слева.