Можно ли получить строку в этой системе перезаписи?

Переписывание системы представляет собой набор правил в виде . Если мы применим это правило к строке мы заменим любую подстроку в подстрокой и наоборот. $A \leftrightarrow B$ $w$ $A$ $w$ $B$

Учитывая начальную строку мы можем получить в системе по следующим правилам: $AAABB$ $BAAB$

$A \leftrightarrow BA$
$BABA \leftrightarrow AABB$
$AAA \leftrightarrow AB$
$BA \leftrightarrow AB$

Есть ли общий алгоритм для этого?

computability term-rewriting Daniil
источник

Буду признателен, если вы добавите больше тегов к этому вопросу или измените набор правил, чтобы он выглядел круче.

Даниил

@ JD Я думаю, что в целом эта проблема переписывания не может быть решена, потому что вы можете смоделировать машину Тьюринга с такой системой переписывания и проблемой деривации == проблема остановки в TM

Даниил

@ JD ах, это имеет смысл, я должен прочитать больше об этом, спасибо!

Даниил

@Daniil и будущие читатели: неразрешимая проблема - это проблема почтовой корреспонденции .

Джмад

По сути это марковская идея алгоритма.

vonbrand

Ответы:

Обратите внимание, что соотношение числа s не меняется. Поскольку одна строка содержит нечетное число а другая четная, они недоступны. $A$ $A$

Я считаю, что в целом (для произвольного набора правил, а не для вашего конкретного примера) это, вероятно, будет неразрешимой проблемой. Если преобразования односторонние (то есть правила вида ), то это так, например, см .: Система тегов . $A \to BA$

Арьябхата
источник

Да, IIRC, это неразрешимо, потому что вы можете смоделировать TM с определенным набором правил переписывания.

Даниил