Membuktikan penutupan di bawah pembalikan bahasa diterima oleh min-heap automata

Ini adalah pertanyaan tindak lanjut dari yang satu ini .

Dalam pertanyaan sebelumnya tentang mesin negara eksotis , Alex ten Brink dan Raphael membahas kemampuan komputasi dari jenis mesin negara yang aneh: min-heap automata. Mereka mampu menunjukkan bahwa himpunan bahasa yang diterima oleh mesin tersebut ( ) bukan merupakan himpunan bagian atau superset dari himpunan bahasa bebas konteks. Mengingat resolusi sukses dan minat jelas dalam pertanyaan itu, saya melanjutkan bertanya beberapa pertanyaan tindak lanjut.$HAL$

Hal ini diketahui bahwa bahasa reguler tertutup di bawah berbagai operasi (kita dapat membatasi diri untuk operasi dasar seperti union, intersection, complement, perbedaan, Rangkaian, bintang Kleene, dan pembalikan), sedangkan bahasa bebas konteks memiliki penutupan yang berbeda sifat (ini ditutup di bawah serikat, Rangkaian, bintang Kleene, dan reversal).

Apakah HAL ditutup dengan pembalikan?

Pertimbangkan bahasa (di mana # 0 ( x ) menunjukkan jumlah nol dalam x ).

Sangat mudah untuk memutuskan menggunakan mesin HAL - mengamati bahwa kebutuhan mesin untuk melacak dua sifat: jumlah angka nol di x vs y dan panjang x , y (vs z ). Hal ini dapat mendorong ke dalam tumpukan untuk setiap nol itu melihat di x (dan kemudian pop untuk setiap nol terlihat di y ); selain itu ia mendorong bit apa pun di x , y (dan kemudian muncul sedikit pun z ). Karena semua tombol ditekan, mereka tidak mengganggu perhitungan. The $L_{\times 2}$$x$$y$$x,y$$z$0$x$0$y$1$x,y$1$z$10$\bot$ berfungsi sebagai pembatas, dan praktis bisa diabaikan.

Sekarang, mari , menjadi bahasa terbalik. Yaitu, L = { z ⊥ y ⊥ x ∣ x , y , z ∈ { 0 , 1 } , # 0 ( x ) = # 0 ( y )  dan  | x | + | y | = Z } Kami akan menunjukkan bahwa tidak ada mesin HAL dapat memutuskan L .$L = L_{\times 2}^R$

Intuisi adalah sebagai berikut. Seperti di atas, mesin harus melacak kedua panjang dan jumlah angka nol di x , y . Namun, dalam hal ini perlu melacaknya secara bersamaan . Ini tidak dapat dilakukan melalui tumpukan. Lebih detail, setelah membaca z , heap berisi informasi tentang panjang | x | + | y | . saat membaca y mesin juga harus menyimpan jumlah nol di dalam y . Namun, informasi ini tidak dapat mengganggu informasi yang sudah ada di tumpukan yang kami harapkan $z$$x,y$$z$$|x|+|y|$$y$$y$$x$menjadi. Sangat intuitif, baik informasi tentang jumlah nol akan "di bawah" informasi tentang panjang , dan kemudian kita tidak dapat mengaksesnya saat membaca x , atau "di atas" informasi itu, membuat yang terakhir tidak dapat diakses, atau dua informasi akan "dicampur" dan menjadi tidak berarti.$x$$x$

Secara lebih formal, kita akan menggunakan semacam argumen "memompa". Yaitu, kami akan mengambil input yang sangat panjang, dan menunjukkan bahwa "keadaan" mesin harus mengulang sendiri selama memproses input itu, yang akan memungkinkan kami untuk "mengganti" input begitu mesin mengulangi "keadaan" -nya.

Untuk bukti formal, kami memerlukan penyederhanaan struktur mesin HAL, yaitu, bahwa itu tidak mengandung "loop" dari -transisi 1 . Dengan asumsi ini kita dapat melihat bahwa untuk setiap simbol input yang diproses mesin, konten heap dapat meningkat / berkurang paling banyak c (untuk beberapa konstanta yang cukup besar c ).$\varepsilon$$^1$$c$$c$

Bukti.
Asumsikan memutuskan L , dan pertimbangkan input yang cukup panjang (katakanlah, dengan panjang 4 n , dengan demikian | x | = | y | = n , | z | = 2 n , dengan mengabaikan ⊥ s selanjutnya). Untuk menjadi beton, memperbaiki z , y dan menganggap bahwa # 0 ( y ) = n / 2 . Perhatikan bahwa ada ($H$$L$$4n$$|x|=|y|=n$$|z|=2n$$\bot$$z,y$$\#_0(y) = n/2$yang berbedax's sehinggaz⊥y⊥x∈L.${n \choose n/2}$$x$$z\bot y \bot x \in L$

Pertimbangkan konten heap segera setelah memproses . Ini berisi paling 3 n c simbol (di mana setiap simbol adalah dari alfabet tetap Γ ), oleh asumsi kita. Namun, ada ($z\bot y$$3nc$$\Gamma$yang berbedax'syang seharusnya diterima (yang secara substansial lebih besar dari jumlah yang mungkin isi yang berbeda untuk heap, dengan meningkatnya ini secara eksponensial, sedangkan jumlah yang berbeda dari tumpukan meningkat polynomially, lihat di bawah). Ambil dua inputx1,x2yang harus diterima, sehingga berikut ini berlaku:${n \choose n/2}$$x's$$x_1,x_2$

1. Awalan panjang dari x 1 memiliki nomor yang berbeda dari nol dari awalan dari x 2 yang sama panjang.$n/2$$x_1$$x_2$
2. $n/2$$x$$x_1$$x_2$$x_1,x_2$$n$$2^{0.8n}$$^2$$x_1,x_2$$(3.5cn)^{|\Gamma|}|Q|$$^3$

$z\bot y \bot x_1^px_2^s$$x_1^p$$x$$n/2$$x_2^s$$x_2$$x_1^px_2^s$$x_1$$x_2$$\#_0(y)$$x_1$$x_2$

$^1$
$^2$ ^{$x_1$$n/2$$n/4$$\log {n \choose k} \approx nH(k/n)$$H()$$H(1/4) \approx 0.81$${n \choose n/4} > 2^{0.8n}$$n$}
$^3$ ^{$\Gamma$$|\Gamma|^n$$n$$n$${n+1 \choose |\Gamma|-1}\approx n^{|\Gamma|}$$|\Gamma|$}