Bahasa unary dikenali oleh counter automata deterministik dua arah

2dca (dua arah deterministik one-counter automata) (Petersen, 1994) dapat mengenali bahasa unary berikut:

Apakah ada bahasa unary nontrivial lain yang dikenali oleh 2dca?

Perhatikan bahwa masih belum diketahui apakah 2dca dapat mengenali ?$\mathtt{SQUARE} = \lbrace 0^{n^2} \mid n \geq 0 \rbrace$

DEFINISI: 2dca adalah otomat terbatas deterministik dua arah dengan penghitung. 2dca dapat menguji apakah nilai penghitung adalah nol atau tidak, dan menambah atau mengurangi nilai penghitung sebesar 1 di setiap langkah.

Ini hanya sebuah ide yang muncul di benak saya ketika membaca Marvin L. Minsky, "Kekuraman Rekursif atas Masalah Tag dan Topik-Topik Lain dalam Teori Mesin Turing"; khususnya teorema Ia yang terkenal:

Teorema Ia: Kita dapat merepresentasikan fungsi rekursif parsial oleh program yang beroperasi pada dua bilangan bulat S 1 dan S 2 menggunakan instruksi I j dari formulir: (i) ADD 1 ke S j , dan pergi ke I j 1 ( ii) SUBTRACT 1 dari S j , jika S j ≠ 0 dan pergi ke I j 1 , jika tidak pergi ke I j 2 Artinya, kita dapat membangun program seperti itu yang dimulai dengan S $f(n)$$S_1$$S_2$$I_j$
$S_j$$I_{j_1}$
$S_j$$S_j \neq 0$$I_{j_1}$$I_{j_2}$
dan S 2 = 0 dan akhirnya berhenti dengan S 1 = 2 f ( n ) dan S 2 = $S_1 = 2^n$$S_2 = 0$$S_1 = 2^{f(n)}$$S_2 = 0$

Jika Anda memiliki DFA dua arah dengan satu penghitung di atas pita tak terbatas (semi) di mana input diberikan secara unary: maka DFA dapat:$\$1^{2^n}000...$

1. baca input unary (dan simpan di konter);
2. kerjakan bagian dari pita dan gunakan jarak dari 1 sebagai penghitung kedua.$0^\infty$$1$

sehingga dapat mensimulasikan mesin dua counter Turing lengkap.

Sekarang, jika Anda memiliki fungsi rekursif yang berjalan dalam waktu T ( n ) pada mesin Turing standar, DFA dua arah dengan satu penghitung yang dimulai pada pita hingga $ 1 m$f(n)$$T(n)$ $\$1^m\$ \;$(di mana dan T ′ ( n ) ≫ T ( n ) ) dapat:$m = 2^n3^{T'(n)}$$T'(n) \gg T(n)$

1. baca input unary (dan simpan di konter);
2. kembali ke simbol paling kiri;
3. bagi penghitung dengan 3 sampai penghitung berisi dengan cara ini: belok ke kanan dari status q z 0 , q z 1 , q z 2 dan kurangi 1; jika penghitung mencapai 0 dalam keadaan q z 0 pergi ke simbol paling kiri menambahkan +1 dan melanjutkan loop pembagian, jika tidak tambahkan 1 (jika dalam keadaan q z 1 ) atau 2 (jika dalam keadaan q z 2 ) dan pergi ke simbol paling kiri menambahkan + 3 (mis. Pulihkan nilai sebelumnya dari penghitung yang tidak habis dibagi 3) dan lanjutkan dengan langkah 4 .;$2^n$$q_{z_0}, q_{z_1}, q_{z_2}$$q_{z_0}$$q_{z_1}$$q_{z_2}$
4. pada titik ini penghitung berisi ;$2^n$
5. hitung menggunakan ruang T ′ ( n ) yang tersedia di sebelah kanan sebagai penghitung kedua (nilai penghitung kedua adalah jarak dari simbol paling kiri $ ).$2^{f(n)}$$T'(n)$$\$$

Jadi dengan pengkodean input khusus yang dijelaskan di atas yang memberikan ruang yang cukup pada rekaman terbatas, DFA dua arah dengan satu counter dan alfabet unary dapat menghitung setiap fungsi rekursif.

Jika pendekatannya benar, akan menarik untuk mempertimbangkan bagaimana memilih atau ketika itu cukup untuk memilih k aneh besar ≫ 2 dan menyandikan input sebagai 1 m , m = 2 n k $T'(n) \gg T(n)$$k \gg 2$$1^m$$m = 2^n k^n$

Dengan non-sepele, saya menganggap Anda maksud bahasa L yang tidak dapat diterima oleh 1dca. Di sini tampaknya bahasa seperti itu:

CENTER = {w | w lebih dari {0,1} * dan w = x1y untuk beberapa x, y sedemikian sehingga | x | = | y |}

Bahasa ini tidak dapat diterima oleh 1dca, tetapi BISA diterima oleh 1nca. Itu bisa diterima oleh 2dca. Detail dibiarkan sebagai latihan.