Apakah mungkin untuk mendapatkan string dalam sistem penulisan ulang ini?

Sistem menulis ulang adalah seperangkat aturan dalam bentuk . Jika kita menerapkan aturan itu ke string kita mengganti substring in dengan substring dan sebaliknya. $A \leftrightarrow B$ $w$ $A$ $w$ $B$

Diberikan string awal dapatkah kita menurunkan dalam sistem dengan aturan berikut: $AAABB$ $BAAB$

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

Apakah ada algoritma umum untuk itu?

computability term-rewriting Daniil
sumber

Saya akan sangat menghargai jika Anda dapat menambahkan lebih banyak tag ke pertanyaan ini, atau mengubah aturan yang diatur agar terlihat lebih keren.

Daniil

@JD Saya pikir, secara umum, masalah penulisan ulang ini tidak dapat diselesaikan, karena Anda dapat memodelkan mesin Turing dengan sistem penulisan ulang dan masalah derivasi == masalah terputusnya TM

Daniil

@ JD ah, itu masuk akal, saya harus membaca lebih lanjut tentang itu, terima kasih!

Daniil

@Daniil dan pembaca di masa mendatang: Masalah yang belum diputuskan yang digunakan adalah masalah surat menyurat .

jmad

Ini pada dasarnya adalah ide algoritma Markov.

vonbrand

Jawaban:

Perhatikan bahwa paritas jumlah huruf tidak berubah. Karena satu string berisi angka ganjil dan yang lainnya genap, mereka tidak dapat dijangkau. $A$ $A$

Saya percaya secara umum (untuk seperangkat aturan yang sewenang-wenang, bukan contoh spesifik Anda), ini mungkin merupakan masalah yang tidak dapat diputuskan. Jika transformasi adalah salah satu cara (yaitu aturan dari bentuk ) demikian, untuk misalnya lihat: Sistem Tag . $A \to BA$

Aryabhata
sumber

Ya, IIRC, ini tidak dapat dipastikan karena Anda dapat memodelkan TM dengan seperangkat aturan penulisan ulang yang spesifik.

Daniil