Ist es möglich, eine Zeichenfolge in diesem Umschreibungssystem abzuleiten?

Überschreibungssystem ist ein Satz von Regeln in Form von . Wenn wir diese Regel auf einen String anwenden, ersetzen wir jeden Teilstring in durch einen Teilstring $A \leftrightarrow B$ $w$ $A$ $w$ $B$ und umgekehrt.

Wenn eine Startzeichenfolge können wir ableiten $AAABB$ $BAAB$ im System mit den folgenden Regeln :

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

Gibt es dafür einen allgemeinen Algorithmus?

computability term-rewriting Daniil
quelle

Ich würde mich freuen, wenn Sie dieser Frage weitere Tags hinzufügen oder den Regelsatz ändern könnten, damit er cooler aussieht.

Daniil

@ JD Ich denke, im Allgemeinen kann dieses Umschreibproblem nicht gelöst werden, weil Sie Turing-Maschine mit einem solchen Umschreibsystem und Ableitungsproblem modellieren können == Stopping-Problem in TM

Daniil

@JD ah, das macht Sinn, ich sollte mehr hineinlesen, danke!

Daniil

@Daniil und zukünftige Leser: Das unentscheidbare Problem ist das Post-Korrespondenzproblem .

jmad

Dies ist im Wesentlichen Markovs Idee des Algorithmus.

vonbrand

Antworten:

Beachten Sie, dass sich die Parität der Anzahl der nicht ändert. Da eine Zeichenfolge eine ungerade Zahl und die andere gerade enthält, sind sie nicht erreichbar. $A$ $A$

Ich glaube im Allgemeinen (für ein beliebiges Regelwerk, nicht für Ihr spezifisches Beispiel), dass dies wahrscheinlich ein unentscheidbares Problem ist. Wenn die Transformationen einseitig sind (dh Regeln der Form ), ist dies der Fall , z. B. siehe: Tag-System . $A \to BA$

Aryabhata
quelle

Ja, IIRC, es ist unentscheidbar, weil Sie ein TM mit einem bestimmten Satz von Umschreibregeln modellieren können.

Daniil