Czy w tym systemie przepisywania można uzyskać ciąg znaków?

Przepisanie systemu jest zestaw reguł w postaci . Jeśli zastosujemy tę regułę do łańcucha , zastąpimy dowolny podciąg in podciągiem i odwrotnie. $A \leftrightarrow B$ $w$ $A$ $w$ $B$

Biorąc pod uwagę początkowy ciąg możemy wyprowadzić w systemie według następujących reguł: $AAABB$ $BAAB$

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

Czy jest na to ogólny algorytm?

computability term-rewriting Daniil
źródło

Byłbym wdzięczny, gdybyś mógł dodać więcej tagów do tego pytania lub zmienić zestaw reguł, aby wyglądał fajniej.

Daniil

@JD Myślę, że ogólnie tego problemu z przepisywaniem nie można rozwiązać, ponieważ można modelować maszynę Turinga z takim systemem przepisywania i problemem pochodnym == problem z zatrzymaniem w TM

Daniil

@JD ah, to ma sens, powinienem przeczytać więcej na ten temat, dzięki!

Daniil

@Daniil i przyszli czytelnicy: nierozstrzygalnym problemem jest problem z korespondencją pocztową .

jmad

Jest to zasadniczo idea algorytmu Markowa.

vonbrand

Odpowiedzi:

Zauważ, że parzystość liczby nie zmienia się. Ponieważ jeden ciąg zawiera nieparzystą liczbę a drugi parzysty, nie są one osiągalne. $A$ $A$

Wierzę ogólnie (w przypadku dowolnego zestawu reguł, a nie konkretnego przykładu), jest to prawdopodobnie nierozstrzygalny problem. Jeśli przekształcenia są jednokierunkowe (tj. Reguły postaci ), tak jest, na przykład patrz: Tag System . $A \to BA$

Aryabhata
źródło

Tak, IIRC, jest nierozstrzygalny, ponieważ możesz modelować bazę TM z określonym zestawem reguł przepisywania.

Daniil