Apakah masalah penghentian dapat diputuskan untuk automata selular satu dimensi 3 simbol?

Saya sudah mencoba mencari tahu apakah masalah penghentian dapat dipilih untuk automata seluler satu dimensi 3-simbol.

Definisi Biarkan menunjukkan konfigurasi sistem pada langkah waktu i . Secara lebih formal f : A ∗ × N → A ∗ , di mana A adalah alfabet.$f(w,i)$$i$$f:A^*\times \mathbb{N} \to A^*$$A$

Definisi. Otomat seluler telah berhenti pada konfigurasi , jika ∀ k ∈ N kita memiliki f ( w , i ) = f ( w , i + k ) .$f(w,i)$$\forall k\in \mathbb{N}$$f(w,i)=f(w,i+k)$

Masalah penghentian untuk automaton seluler yang diberikan adalah sebagai berikut:

Input: kata yang terbatas Pertanyaan: akan otomat berhenti di beberapa negara s ?$w$
$s$

Automata seluler dasar (dengan 2 simbol) didefinisikan di sini . Saya fokus pada jenis yang sama dari automata seluler, kecuali bahwa saya tertarik pada kasus CA dengan 3 simbol, bukan hanya 2 simbol.

Mulai sekarang, saya akan menunjukkan aturan saya dalam bentuk , yang berarti bahwa 3 simbol tetangga menghasilkan yang lain di bawahnya.$***\to*$

Masalah penghentian adalah decidable untuk automata seluler dasar, 2-simbol

Saya akan menggunakan untuk menunjukkan sel putih dan 1 untuk menunjukkan yang hitam.$0$$1$

Jika kita memiliki aturan , 001 → 1 , 100 → 1 kita tahu otomatanya tidak akan berhenti. Karena dengan aturan pertama, karena kisi kita tidak terbatas, kita akan selalu memiliki 3 sel putih yang akan menghasilkan sel hitam. Dengan aturan kedua dan ketiga kata akan meluas ke samping dan otomaton tidak akan pernah berhenti.$000 \to 1$$001 \to 1$$100 \to 1$

Dalam sisa kasus kita dapat membiarkannya berkembang selama langkah dan melihat apakah itu berhenti. Jika itu berhenti, maka ok, berhenti, jika tidak maka itu mengulangi beberapa kombinasi dan terjebak dalam satu lingkaran, jadi kita juga dapat menyimpulkan bahwa itu tidak akan berhenti.$2^n$

Apa yang saya temukan untuk kasus 3 simbol

Jelas bahwa itu tidak akan berhenti jika kita memiliki aturan atau 000 → 2 . Tetapi aturan samping dari formulir 00 x → y dan x 00 → y lebih sulit untuk dianalisis, karena bagaimana jika kita memiliki aturan 002 → 1 dan 001 → 0 ?$000 \to 1$$000 \to 2$$00x \to y$$x00 \to y$$002 \to 1$$001 \to 0$

Inilah yang saya pikirkan:

mari kita pertimbangkan semua kombinasi aturan tersebut:

1. dan 002 → $001 \to 0$$002 \to 0$
2. dan 002 → $001 \to 0$$002 \to 1$
3. dan 002 → $001 \to 0$$002 \to 2$
4. dan 002 → $001 \to 1$$002 \to 0$
5. dan 002 → $001 \to 1$$002 \to 1$
6. dan 002 → $001 \to 1$$002 \to 2$
7. dan 002 → $001 \to 2$$002 \to 0$
8. dan 002 → $001 \to 2$$002 \to 1$
9. dan 002 → $001 \to 2$$002 \to 2$

Saya tidak menulis case untuk aturan form , karena itu simetris.$x00 \to y$

Jadi, dalam kasus pertama jelas bahwa kata input tidak akan meluas ke sisi, karena aturan simbol sisi menghasilkan nol.

Dalam kasus 5, 6, 8, 9 jelas bahwa robot tidak akan pernah berhenti, karena kata input akan diperluas.

Kasus 2,3,4,7 lebih menarik. Pertama, mari kita perhatikan, bahwa case 2 mirip dengan case 7 dan case 3 mirip dengan case 4. Jadi, mari kita pertimbangkan case 2 dan 3 untuk ringkas.

Saya akan mempertimbangkan kasus 3 terlebih dahulu, karena lebih mudah.

Kami memiliki dan 002 → 2 . Jelas bahwa jika simbol pertama atau terakhir dari kata input kami adalah 2 , maka kita dapat menyimpulkan bahwa automaton tidak akan berhenti. Tetapi jika mereka adalah '1', maka kita harus melihat lebih banyak barang, khususnya, mari kita lihat aturan yang dapat mengubah simbol terakhir atau pertama menjadi 2 , karena jika kita memiliki itu, maka setelah mereka menghasilkan itu 2 , kita dapat menyimpulkan bahwa robot tidak akan berhenti. (kata akan meluas ke samping)$001 \to 0$$002 \to 2$$2$$2$$2$

Berikut semua kombinasi yang perlu kita pertimbangkan:

010 011 012
 0   0   0
 0   0   1
 0   0   2
 0   1   0
 0   1   1
........... etc

Penjelasan tentang apa yang terjadi jika kita memiliki triple pertama dari tabel di atas

Kami memiliki kata , tertulis di grid. Simbol pertama dan terakhir adalah 1 . Katakanlah kita memiliki aturan 010 → 0 , 011 → 0 , 012 → 0 (rangkap tiga pertama) dari atas. Kemudian kita tahu bahwa dengan setiap langkah selanjutnya kata input kita akan menjadi lebih kecil dengan 2 simbol, karena aturan ini menghapus simbol pertama dan terakhir, tetapi jika pada beberapa titik kita mendapatkan 2 , maka aturan 002 → 2 akan membuat kata bertambah ke satu sisi atau yang lain (atau keduanya) dan otomaton tidak akan pernah berhenti. Jadi, secara keseluruhan, dalam hal ini kita dapat membiarkan otomat melakukan | w | $w$$1$$010 \to 0$$011 \to 0$$012 \to 0$$2$$002 \to 2$ langkah, dan jika kata itu menjadi kosong, maka automaton berhenti, jika tidak, maka tidak.$|w|/2$

Kasus umum 3

Aku umum itu dan melihat bahwa kita hanya dapat membiarkan otomat jangan langkah dan jika di salah satu dari langkah-langkah kita memiliki 2 sebagai simbol pertama atau terakhir, maka robot tidak akan berhenti. Jika itu tidak terjadi dan automaton masih tidak berhenti, maka itu mengulangi beberapa konfigurasi, sehingga macet dalam satu lingkaran dan tidak akan berhenti. Jika berhenti, maka berhenti.$3^n$$2$

Di mana saya terjebak

Sekarang mari kita pertimbangkan kasus 2.

Kami memiliki aturan dan 002 → 1 .$001 \to 0$$002 \to 1$

Dan di sinilah saya terjebak dan tidak tahu harus berbuat apa.

Saya juga menulis daftar aturan yang dimulai dengan . Saya menulis itu, karena sepertinya itu adalah hal pertama yang harus saya analisis, karena walaupun kita memiliki kata input dengan simbol pertama atau terakhir (atau keduanya) sebagai 2 , pada langkah selanjutnya 2 - s itu akan berubah menjadi 1 . Dan kita harus berurusan dengan aturan formulir 01 x → y .$1$$2$$2's$$1$$01x \to y$

Ini tabelnya:

010 011 012
 0   0   0
 0   0   1
 0   0   2
 0   1   0
 0   1   1
 0   1   2
 0   2   0
 0   2   1
 0   2   2
 1   0   0
 1   0   1
 1   0   2
 1   1   0
 1   1   1
 1   1   2
 1   2   0
 1   2   1
 1   2   2
 2   0   0
 2   0   1
 2   0   2
 2   1   0
 2   1   1
 2   1   2
 2   2   0
 2   2   1
 2   2   2

Jelas juga, bahwa jika di antara 27 aturan kami, kami memiliki tiga dari tabel ini di mana tidak ada aturan yang memperoleh angka , maka kami tidak perlu khawatir dan hanya dapat membiarkan robot berevolusi selama 3 n langkah, karena ia menang ' t benar-benar berkembang, karena aturan samping tidak akan menghasilkan 2 .$2$$3^n$$2$

Tetapi melihat tiga kali lipat yang memiliki , sebenarnya sangat sulit untuk dianalisis, dan apakah kata tersebut akan meluas atau tidak juga tampaknya tergantung pada kata yang dimasukkan.$2$

Bisakah kalian memberitahuku cara mengatasi ini? Saya tidak bisa membungkus kepala saya dengan ini.

Atau, jika automaton seluler 3 simbol ini terlihat seperti sesuatu yang masalah penghentiannya telah terbukti tidak dapat diputuskan, bagaimana saya dapat mengurangi sesuatu menjadi 3 simbol automata seluler?

Saya telah menemukan artikel ini: http://www.dna.caltech.edu/~woods/download/NearyWoodsMCU07.pdf dan akan menunjukkan bagaimana membuktikan bahwa masalah penghentian tidak dapat diputuskan untuk automata seluler 15-simbol.

Mari kita lihat instruksi khas mesin Turing, yang kita miliki:

1) $q,x\to p,y,L$

2) $q,x\to p,y,R$

Yang pertama mengatakan bahwa jika otomaton melihat simbol dalam keadaan q , maka kita mengganti x dengan y , beralih ke keadaan p dan bergerak ke kiri, yang kedua mengatakan hal yang sama, tetapi bergerak ke kanan.$x$$q$$x$$y$$p$

Mari kita berasumsi bahwa TM abjad adalah , seperangkat aturan adalah R dan himpunan negara adalah Q . Sekarang, mari kita buat alfabet baru untuk otomat seluler kita, itu akan menjadi sebagai berikut: Σ = A ⋃ Q ⋃ { q ′ | ∀ q ∃ r ∈ R , r = p , x → q , y , L } . Dengan kata lain, dalam alfabet baru kami akan menyertakan alfabet TM, alfabet status TM dan untuk setiap negara $A$$R$$Q$$\Sigma=A\bigcup Q\bigcup \{q'|\forall q \exists r\in R, r=p,x\to q,y,L\}$$q$, sedemikian sehingga ada aturan kita akan memasukkan q ′ .$p,x\to q,y,L$$q'$

$s=...xabqzyk...$$q\in Q$$q$$z$

Mari kita lihat bagaimana kita dapat mensimulasikan operasi TM. Mari kita pertimbangkan yang kedua dulu:

$q,z\to p,y,R$

$s=...xabqzyk...$$...xabypyk...$

$qz\alpha\to p, \forall \alpha \in \Sigma$

$\alpha qz\to y, \forall \alpha \in \Sigma$

Kasus pertama sedikit lebih rumit, kita memiliki:

$q,z\to p,y,L$

$s=...xabqzyk...$$...xapbyyk...$$abq\to p$$abq$

Langkah pertama:

$qz\alpha\to y, \forall \alpha \in \Sigma$

$\alpha qz\to p', \forall \alpha \in \Sigma$

tahap kedua:

$\alpha \beta p'\to p, \forall \alpha, \beta \in \Sigma$

$\alpha p' \beta\to \beta, \forall \alpha, \beta \in \Sigma$

Adapun semua aturan CA lainnya, yang tidak ada aturan dalam TM, kami akan menulis sebagai berikut:

$\alpha \beta \gamma \to \beta, \forall \alpha,\beta,\gamma \in \Sigma$

$U_{6,4}$

$q'$$p,x\to q,y,L$$u_1, u_3, u_4, u_5, u_6$

Jadi, sekarang ada celah antara 2 dan 15 simbol (eksklusif), yang tidak kita ketahui.