Kelas bahasa yang dapat dikenali oleh single-tape 3-state TM

9

Untuk sementara saya ingin tahu tentang Mesin Turing dengan tepat satu pita dan tepat 3 status (yaitu status awal , status terima , dan status tolak ). Perhatikan bahwa saya membolehkan abjad pita yang terbatas (terbatas) (yaitu, alfabet pita tidak terbatas sama dengan alfabet masukan).q a c c e p t q r e j e c tq0qacceptqreject

Untuk kenyamanan, hubungi kelas bahasa yang dikenali oleh TM . Saya punya beberapa pertanyaan tentang kelas ini:C3

  1. Apakah sebelumnya telah dipelajari?C3
  2. Apakah diketahui setara dengan kelas minat / kompleksitas / lainnya?C3
  3. Apakah kelas kuat untuk perubahan dalam model. Misalnya, jika TM yang digunakan dibiarkan tetap di tempatnya selama satu transisi (sebagai lawan untuk selalu bergerak ke kiri atau kanan) atau jika pita dibuat menjadi tak terbatas di kedua arah, bukan hanya ke kanan, apakah kelas bahasa yang dikenali oleh perubahan 3-pita 1-pita 3-negara?C3
  4. Bagaimana dengan kelas bahasa reguler, ? (Secara khusus, apakah setiap bahasa reguler di ?) R e g u l a r C 3C3RegularC3

Pencarian (agak sepintas) hanya memunculkan posting cs.stackexchange ini yang relevan tetapi tidak menjawab pertanyaan saya dan makalah ini , yang saya belum baca secara cukup detail untuk memastikan bahwa itu berkaitan dengan kelas tepatnya daripada kelas kelas serupa tetapi berbeda (makalah ini mengklaim untuk membuktikan bahwa (1) setiap bahasa dalam dapat dipilih dan (2) bahwa dan adalah kelas yang berbeda dengan persimpangan yang tidak kosong). Seperti yang ditunjukkan dalam komentar dari pos pertukaran cs.stackexchange, jenis TM ini dapat dianggap sebagai automata seluler yang sangat khusus, jadi mungkin seseorang yang mengetahui literatur tentang teori otomat seluler dapat membantu.C 3 C 3 R e g u l a rC3C3C3Regular

Mikhail Rudoy
sumber
1
Jika Anda hanya memiliki satu status non-terminating dan satu tape (input tape), maka mesin Anda tidak dapat mengingat apa pun yang dibaca. Jadi, ia dapat menerima atau menolak input yang mengandung simbol pasti dari alfabet input.
David G
4
Mesin tidak dapat mengingat apa yang dibacanya, tetapi ia dapat menulis ulang apa yang dibaca dengan sesuatu yang lain. Jadi saya tidak benar-benar mengerti mengapa karakterisasi yang Anda berikan benar. (Yaitu saya bisa memikirkan mesin sederhana yang menerima dan menolak 011 ; di sini perilaku tidak sepenuhnya ditentukan oleh simbol yang ada di input). 01011
Mikhail Rudoy
1
Anda benar, intuisi saya salah.
David G

Jawaban:

7

Binatang itu sangat kuat , misalnya kita dapat membangun TM yang menerima setiap string bentukM

LY={r0n1mAmn}

dan menolak setiap string formulir

LN={r0n1mAm>n}

Idenya adalah untuk mengubah pertama menjadi R dan kemudian membiarkan kepala mencapai tengah string kemudian melakukan "stateless" zig-zag; jika mencapai A sebelum R maka ia menerima.rRAR

Deskripsi informal:

  • pada tulis R dan ke kanan (bersiap untuk menolak)rR
  • pada tulis c dan bergerak ke kanan (bergerak ke tengah)0c
  • pada tulis > dan bergerak ke kiri (tandai 1 , bersiap untuk persimpangan kiri-ke-kanan berikutnya, dan ke kiri)1>1
  • pada tulis < dan bergerak ke kanan (tandai 0 , bersiap untuk persimpangan kanan-ke-kiri berikutnya, dan ke kanan)c<0
  • pada write > dan ke kiri (persimpangan kiri-ke-kanan, bersiap untuk kanan-ke-kiri berikutnya)<>
  • pada tulis < dan ke kanan (persimpangan kanan-ke-kiri, siapkan kiri-ke-kanan berikutnya)><
  • pada accept, on R rejectAR
  • pada kosong tolakb

Contoh:

  :r 0 0 0 1 1 A
   R:0 0 0 1 1 A
   R c:0 0 1 1 A
   R c c:0 1 1 A
   R c c c:1 1 A
   R c c:c > 1 A
   R c c <:> 1 A
   R c c < <:1 A
   R c c <:< > A
   R c c:< > > A
   R c:c > > > A
   R c <:> > > A
   ...
   R c < < < <:A ACCEPT

Teknik zig-zag ini digunakan dalam mesin Universal Turing 2-negara terkecil (memiliki 18 simbol) yang dibangun oleh Rogozhin (Rogozhin 1996. TCS, 168 (2): 215-240)).

Beberapa perhatian harus diberikan untuk membuktikan bahwa berhenti pada semua input (perlu diketahui bahwa ia menolak pada input kosong dan semua simbol yang tidak berhenti "konvergen" ke < atau > yang tidak dapat mengarah ke loop tak terbatas).M<>

Seperti dikomentari oleh DavidG, bahasa dikenali oleh M adalah superset dari L Y (yaitu L YL ( M ) ) tetapi tidak mengandung string apa pun dari L N (yaitu L ( M ) L N = ) dan - seperti yang dikomentari oleh MikhailRudoy - ini cukup untuk membuktikan bahwa L ( M ) tidak teratur.L(M)MLYLYL(M)LNL(M)LN=L(M)

Memang jika teratur maka juga L ( M ) { r 0 1 A } = L Y = { r 0 n 1 m A m n } akan menjadi biasa (yang bukan oleh aplikasi sederhana dari lemma pemompaan); mengarah ke kontradiksi.L(M)L(M){r01A}=LY={r0n1mAmn}

Jadi tidak teratur .L(M)

... Tapi seperti semua superhero memiliki sebuah tumit Achille: itu bahkan tidak bisa mengenali biasa:C3

L={12n}

Informal dapat menggunakan hanya yang paling kiri ( b adalah simbol kosong) atau orang kanan 1 b . . . sebagai pengait dan "mengembang" ke arah yang lain; tetapi Penerimaan akhir atau Tolak tidak dapat berada pada simbol kosong dari sisi yang berlawanan, sehingga hal itu dapat dilakukan hanya pada bagian dalam dari 1 detik dan mulai dari input yang cukup lama dapat "dipalsukan" dengan membukanya dengan satu.b1...b1b...1

Akhirnya - setelah membaca koran - saya dapat mengkonfirmasi bahwa satu-negara TM yang dijelaskan di dalamnya cocok dengan kelas ... (jadi tidak ada yang baru di sini :-) ... dan bahasa yang digunakan oleh penulis untuk membuktikan bahwa ia mengandung bahasa non-reguler sangat mirip dengan bahasa saya.C3

Marzio De Biasi
sumber
1
Saya sangat suka jawabannya (+1). Namun, TM yang dijelaskan menerima bahasa yang berbeda. Itu, misalnya, menerima juga string rrrrr00011AAAA, r000000r0000r0000r00011A, r00011A11111111 (setelah A itu bisa apa saja, bukan yang) ...
David G
@ David G: Anda benar! Saya tidak terlalu memikirkannya ... Saya mencoba memperbaikinya.
Marzio De Biasi
4
Sebenarnya, bahkan melalui bukan bahasa diakui oleh TM dijelaskan, bahasa yang pasti tidak biasa: jika itu TM adalah M , maka L ( M ) r 0 * 1 * A = L sehingga bukti singkat dengan kontradiksi (jika L ( M ) teratur maka L ( M ) r 0 1 A = L juga akan teratur; kontradiksi) dapat menunjukkan bahwa L ( M ) tidak teratur.LML(M)r01A=LL(M)L(M)r01A=LL(M)
Mikhail Rudoy
3
@MikhailRudoy: ya! Saya punya ide yang sama. Saya membuka cerita untuk mengedit jawaban, dan melihat komentar Anda. Mari kita lihat apakah saya dapat menulis ulang jawaban dengan mempertimbangkan komentar Anda ...
Marzio De Biasi
5

Saya meremehkan kekuatan ... sebenarnya itu tidak terlalu jauh dari perhitungan Hyper !C3

(Saya memposting ini sebagai jawaban terpisah untuk kejelasan yang lebih baik)

Kita dapat membangun satu mesin Turing negara yang menerima string dari bentuk:M

LY={a0n1mRm2n}

dan menolak string dari formulir:

LN={a0n1mRm<2n}

Gagasan dan konstruksinya mirip dengan yang ada di jawaban sebelumnya: ubah pertama menjadi A , biarkan kepala mencapai tengah string kemudian lakukan zig-zag "stateless", tetapi transisi "implement" a "binary counter" "pada paruh pertama dengan cara ini: pada Z (Nol) memantulkan kepala kembali ke kanan , dan mengubah Z menjadi S (Satu) saat berikutnya kepala mencapai S , mengubahnya menjadi a ) dan biarkan kepala bergerak ke kiri; ketika kepala mencapai yang ) mengubahnya ke Z . Bagian kedua dari string berperilaku seperti penghitung unary.aAZZSS))Z

Transisinya adalah:

  • pada tulis R dan ke kanan (bersiap untuk menolak)rR
  • pada tulis Z dan bergerak ke kanan (bergerak ke tengah, atur penghitung biner ke 0 ..)0Z
  • pada tulis > dan bergerak ke kiri (tandai 1 dan kurangi penghitung unary, bersiap untuk persimpangan kiri-ke-kanan berikutnya, dan bangkit kembali ke penghitung biner)1>1
  • pada tulis < dan ke kanan (persimpangan kanan-ke-kiri pada bagian kedua dari string, bersiap untuk kiri-ke-kanan berikutnya)><
  • pada write > dan ke kiri (persimpangan kiri-ke-kanan pada bagian kedua dari string, bersiap untuk kanan-ke-kiri berikutnya)<>
  • pada tulis S dan bergerak ke kanan (mengubah digit ke satu dan bangkit kembali ke kanan menuju penghitung unary)ZS
  • pada tulis ) dan bergerak ke kiri (kosongkan digit, dan biarkan kepala bergerak ke kiri seperti "membawa", mempersiapkan kiri-ke-kanan berikutnya dari bagian pertama)S)
  • aktif tulis Z dan gerakkan ke kanan (atur nol yang akan menyebabkan pantulan, dan biarkan kepala bergerak ke kanan))Z
  • pada accept, on R rejectAR
  • pada kosong tolakb

Contoh:

 :a 0 0 0 1 1 1 1 1 1 1 1 R
  A:0 0 0 1 1 1 1 1 1 1 1 R
  A Z:0 0 1 1 1 1 1 1 1 1 R
  ...
  A Z Z Z:1 1 1 1 1 1 1 1 R
  A Z Z:Z > 1 1 1 1 1 1 1 R
  A Z Z S:> 1 1 1 1 1 1 1 R
  A Z Z S <:1 1 1 1 1 1 1 R
  A Z Z S:< > 1 1 1 1 1 1 R
  A Z Z:S > > 1 1 1 1 1 1 R
  A Z:Z ) > > 1 1 1 1 1 1 R
  A Z S:) > > 1 1 1 1 1 1 R
  A Z S Z:> > 1 1 1 1 1 1 R
  ...
  A Z S:Z > > > 1 1 1 1 1 R
  ...
  A Z S S < < <:1 1 1 1 1 R
  ...
  A S:) ) > > > > 1 1 1 1 R
  ...
 :A ) ) ) > > > > > > > > R ---> ACCEPT

Perhatian harus diberikan untuk membuktikan bahwa berhenti pada semua input (perlu diketahui bahwa ia menolak pada input kosong dan semua simbol "siklus" tanpa henti melalui ( , S , Z atau < , > yang tidak dapat mengarah ke loop tak terhingga) ).M(,S,Z<,>

Bahasa adalah superset dari L Y ( L YL ( M ) ) dan tidak mengandung string dari L N ( L ( M ) L N = ).L(M)LYLYL(M)LNL(M)LN=

Misalkan adalah Context Free , maka - dengan properti penutupan CFL, memotongnya dengan bahasa biasa { r 0 1 A } menghasilkan bahasa CF:L(M){r01A}

L(M){r01A}={a0n1mRm2n}=LY

Tetapi dengan aplikasi sederhana dari Ogden's Lemma untuk CFL kita dapat membuktikan bahwa : cukup pilih s yang cukup panjang L Y dan tandai semua 0 s; setidaknya satu nol dapat dipompa dan berapapun jumlah 1 s dalam string pemompaan, pertumbuhan eksponensial 2 n mengarah ke string L Y ).LYCFLsLY01s2nLY

Jadi bukan Gratis Konteks .L(M)

... sekarang saya bertanya-tanya apakah ini jawaban "reinventing the wheel" yang lain, atau ini adalah hasil (kecil) yang baru.

Marzio De Biasi
sumber
Nah, bahasa di sini bisa dihitung dalam kelas serendah coNLOGTIME, jadi tidak persis membutuhkan komputasi yang berlebihan. (Bahkan, dan L N dapat dipisahkan bahkan dalam DLOGTIME.)L.YL.N
Emil Jerabek
@ EmilJeřábek: Saya berkata "tidak terlalu jauh" ... jangan menghambat ambisi kelas kecil itu ... :-)
Marzio De Biasi
2

Dalam jawaban ini diasumsikan bahwa mesin Turing memiliki kaset infinite dua arah. Klaim tidak berlaku untuk rekaman tak terbatas satu arah.

Pertama-tama, saya mendefinisikan kelas bahasa sebagai kelas semua bahasa yang dapat dipilih oleh mesin Turing satu-pita dengan 3 status ( C 3 didefinisikan sebagai kelas bahasa yang dikenali oleh mesin Turing satu-tape dengan 3 negara). Saya memperkenalkan kelas C 3 karena dalam jawaban asli saya, saya secara tidak sadar menukar kelas C 3 dan C 3 (saya hanya mempertimbangkan kelas C 3 ).C3C3C3C3C3C3

Jawaban ini lebih melengkapi jawaban @MarzioDeBiasi. Dia menunjukkan bahwa kelas dan C ' 3 tidak terkandung dalam CFL dan dengan demikian mengandung bahasa cukup menarik. Namun, seperti yang akan saya tunjukkan dalam posting ini, setiap bahasa L dalam C 3 memiliki properti yang diset { 1 n ; n N{ 0 } } adalah baik dalam L atau yang pelengkap L C . Jadi C 3C3C3LC3{1n;nN{0}}LLCC3juga sangat membatasi, misalnya. itu hanya berisi bahasa unary sepele , { ε } , { 1 n ; n N } dan { 1 n ; n N{ 0 } } . Kelas C 3 berisi sedikit lebih banyak bahasa unary. Namun, ia berpendapat bahwa jika L C 3 dan 1 nL untuk n 1 , maka 1{}{ε}{1n;nN}{1n;nN{0}}C3LC31nLn1 untuk semua m n . 1mLmnAkibat wajar sederhana adalah bahwa tidak semua bahasa reguler berada di atau di C 3 . Juga bahasa{1}tidak dalam C 3 atau dalam C 3 .C3C3{1}C3C3


Untuk klaim (dalam huruf tebal) tentang , cukup membuktikan bahwa mesin Turing satu-pita M dengan 3 status yang selalu berhenti menerima atau menolak semua string dari { 1 n ; n N{ 0 } } . Misalkan string dari bentuk 1 n , n N{ 0 } , diberikan kepada M . Ada tiga kasus:C3M{1n;nN{0}}1nnN{0}M

1) Ketika membaca 1, ia menerima atau menolak.M

2) Ketika membaca 1, ia menggerakkan kepala ke kiri. MJika kita ingin menghentikan input ini, ia harus menerima, menolak atau bergerak ke kanan pada simbol kosong. Karenanya, ia tidak pernah mengunjungi sel di sebelah kanan sel awal rekaman itu. Jika mau, itu akan berjalan selamanya pada input 1.M

3) Ketika membaca 1, ia menggerakkan kepala ke kanan. MMaka setelah langkah, isi rekaman adalah A n di mana A adalah beberapa simbol dari alfabet tape dan kepala M adalah pada simbol paling kiri kosong di sebelah kanan A terakhir . Jika kita ingin M menghentikan input ini, ia harus menerima, menolak atau bergerak ke kiri pada simbol kosong. Seperti dalam kasus 2), kepala M sekarang tidak akan pernah mengunjungi sel langsung di sebelah kiri paling kanan A . Jika ya, maka M akan berjalan selamanya pada input 1.nAnAMAMMAM

Jelas bahwa dalam ketiga kasus menerima semua string dari set { 1 n ; n N{ 0 } } atau menolak semuanya.M{1n;nN{0}}


Bukti klaim (dicetak tebal) tentang mengikuti baris yang sama seperti di atas. Kami mengambil mesin Turing satu-pita 3-negara M yang menerima string 1 n untuk beberapa n 1 . Misalkan M diberi input 1 m untuk m n . Kita harus membuktikan bahwa M menerima input ini. Kami memiliki 3 kasus:C3M1nn1M1mmnM

1) Ketika membaca 1, ia menerima.M

2) Ketika membaca 1, ia menggerakkan kepala ke kiri. MKarena menerima input 1 n , ia harus menerima atau bergerak ke kanan pada simbol kosong. Oleh karena itu, tidak pernah kunjungan yang n th sel di sebelah kanan sel awal. Jika mau, itu akan berjalan selamanya pada input 1 n .M1nn1n

3) Ketika membaca 1, ia menggerakkan kepala ke kanan. MOleh karena itu setelah langkah , isi rekaman adalah A m di mana A adalah beberapa simbol dari alfabet tape dan kepala M adalah pada simbol paling kiri kosong di sebelah kanan A terakhir . Karena M menerima input 1 n , ia harus menerima atau bergerak ke kiri pada simbol kosong. Seperti dalam kasus 2), kepala M sekarang tidak akan pernah mengunjungi sel ke- n di sebelah kiri A paling kanan . Ini karena pada input 1 n , MmAmAMAM1nMnA1nM tidak mengunjungi sel langsung di sebelah kiri sel awal, karena mengandung simbol kosong dan jika akan membacanya, itu akan berjalan selamanya.

Jelas bahwa dalam ketiga kasus menerima semua string dari set { 1 m ; m n } .M{1m;mn}

David G
sumber
Pertama-tama, tidak ada pertanyaan yang mengatakan bahwa M harus menghentikan semua input, sehingga mengacaukan beberapa logika dalam jawaban ini. Di luar itu, logika dalam beberapa kasus tidak masuk akal bagi saya. Misalnya, dalam kasus 3, jika M bergerak ke kiri dengan posisi kosong dan A, maka M akan mengunjungi sel langsung ke kiri dari A paling kanan (berbeda langsung dengan klaim dari jawaban.)
Mikhail Rudoy
Σ={1}k st 1kL.(M.)L.(M.)={1nn>0}
@MikhailRudoy, ​​untuk pertama-tama mengklarifikasi kasus 3: jika kepala bergerak ke kiri pada simbol A dan kosong, maka akan bergerak ke kiri selamanya dan tidak akan berhenti. Jika pernah (katakan setelah 100 langkah) mengunjungi sel langsung ke kiri dari A paling kanan, maka dalam kasus input 1 tidak pernah berhenti (dalam hal ini sel langsung ke kiri dari A paling kanan akan berisi simbol kosong).
David G
@MikhailRudoy, ​​memang benar bahwa saya berasumsi bahwa mesin Turing harus berhenti. Saya akan mengedit jawaban untuk menyertakan juga kemungkinan itu berjalan selamanya. Hasilnya serupa.
David G
3
@MikhailRudoy: BTW masalah hatling adalah decidable untuk 1 mesin Turing negara; lihat Gabor T. Herman, Masalah penghentian seragam untuk mesin turing umum satu-negara . Model yang dijelaskan ada sedikit berbeda dengan Anda: TM menerima jika berakhir pada konfigurasi fana (tidak ada Terima / Tolak); tetapi hasilnya juga berlaku untuk model Anda (Hentikan saja TM pada simbol yang mengarah ke status Terima / Tolak tambahan).
Marzio De Biasi